- 1大数据TensorFlow深度学习——基于BERT+LSTM+CRF深度学习识别模型医疗知识图谱问答可视化系统(完整系统源码+PPT+详细开发文档+论文+源码解析)_基于医疗知识图谱的语音问答机器人可视化界面
- 2python+django+mysql电影院选座订票系统毕业设计毕设开题报告_django开题报告
- 3结构化存储和OLE对象
- 4【转行互联网】转行互联网必看答疑
- 5uniapp隐藏状态栏并强制横屏_uniapp隐藏导航栏并全屏
- 6mac os使用cpolar配置内网访问（内网穿透）教程_macos14下cpolar实现内网穿透
- 7手动添加Git Bash Here到右键菜单（超详细）_gitbash添加到右键
- 8Android Studio上编译JNI程序_android studio编译jni
- 9用Python进行数据清洗，这7种方法你一定要掌握_python 聚类后 剔除某个类
- 10Linux Audio Alsa (2) alsa.conf
算法笔记（Java）——动态规划_java动态规划
赞
踩
动态规划方法论
动态规划，英文：Dynamic Programming，简称DP，如果某一问题有很多重叠子问题，使用动态规划是最有效的。
所以动态规划中每一个状态一定是由上一个状态推导出来的，这一点就区分于贪心，贪心没有状态推导，而是从局部直接选最优的，
动规和递归的区别是动规不是暴力的，产生的中间结果用数组记录起来，比较高效，详情可以看文章：
动态规划的解题步骤：
- 确定dp数组（dp table）以及下标的含义
- 确定递推公式
- dp数组如何初始化
- 确定遍历顺序
- 举例推导dp数组（当出现问题时用此方法调试）
动态规划常见题型：
- 背包问题：难点在遍历顺序那里，01背包和完全背包 排列组合问题等等的遍历顺序
- 子序列问题：难点在思考出dp数组的含义，甚至很可能都看不出要用dp来做
- 股票问题：难点在理解状态有几种，dp数组能否表示所有状态吗，持有和卖出的区别
- 打家劫舍：不太难好像
个人觉得最难理解的就是遍历顺序，甚至比确定递推公式还难，如果迷糊了可以手写dp数组来理解，请注意一维和二维还是有点不一样的，可以都试试。
简单示例：
class Solution {
public int climbStairs(int n) {
if(n<=2){
return n;
}
int[] count = new int[n+1]; // 1.dp[i]： 爬到第i层楼梯，有dp[i]种方法
count[1] = 1;
count[2] = 2;
for(int i=3;i<=n;i++){
count[i] = count[i-1]+count[i-2]; // 2.dp[i] = dp[i - 1] + dp[i - 2]
}
return count[n];
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
背包问题
01背包
有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。
01背包和完全背包的区别就是物品只能放一次
例如：
物品为：
物品 重量 价值
物品0 1 15
物品1 3 20
物品2 4 30
问背包能背的物品最大价值是多少？
二维dp数组
dp[i][j] 表示从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])
含义是：
遍历到物品i的时候，背包容量为j的最大价值分为放i和不放i两种情况 dp[i-1][j]为不放i，dp[i - 1][j - weight[i]] + value[i])为放i
遍历顺序都可以，可以先遍历背包再遍历物品，也可以先遍历物品再遍历背包。因为根据递推公式，求当前dp值是用的上一行的元素或者左上的元素，因此从左到右和从上到下两种方式均可。
初始化：要初始化第一行，因为递推公式有i-1。
推导dp数组
// weight数组的大小 就是物品个数
for(int i = 1; i < weight.size(); i++) { // 遍历物品
for(int j = 0; j <= bagweight; j++) { // 遍历背包容量
if (j < weight[i]) dp[i][j] = dp[i - 1][j];
else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
一维dp数组
从二维dp数组可知，确定当前dp值只需要上面或者左上的元素，那么可以使用滚动数组的方式，只使用一个一维数组。
- 在一维dp数组中，dp[j]表示：容量为j的背包，所背的物品价值可以最大为dp[j]。
- 递推公式：dp[j]是不选 后面那个是选，对应二维的上面的元素和左上的元素
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
- 无需初始化
- 遍历顺序：跟二维不一样，先遍历物品，再方向遍历背包。反向是避免覆盖，因为如果左面的dp值更新了以后，对应二维情况是同一行左面的值，而不是上一行最面的值，会重复选取，需要重复选取的完全背包才可以正向遍历
- 打印dp数组
for(int i = 0; i < weight.size(); i++) { // 遍历物品
for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
}
}
- 1
- 2
- 3
- 4
- 5
- 6
PS：之前一直认为，为什么一维情况可以直接从右向左遍历呢，右边的dp[j]难道不需要左边的值吗，后来发现确实不需要，只需要上一行同列的值和上一行左边的值，可以打印数组进行尝试理解，注意是01背包，物品只能放进去一次。
背包问题在题目中并不明显，需要自己抽象出题目的特点来：
给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
示例 1：
输入：nums = [1,5,11,5]
输出：true
解释：数组可以分割成 [1, 5, 5] 和 [11] 。
乍一看看不出来是个背包问题，但是要想分割成等和子集，一定有两部分的和要相等的，而且两部分的和为sum的一半，所以可以往容量为 sum/2的背包里装物品，看看能不能装满：
class Solution { public boolean canPartition(int[] nums) { // 背包问题的解决公式：二维 dp[i][j] = dp[i-1][j]+dp[i-1][j-nums[i]]+nums[i] // 一维：dp[j] = dp[j]+dp[j-nums[i]]+nums[i] // 1.确定dp数组和下标的含义 // 2.确定递推公式 // 3.确定初始化方式 // 4.确定遍历顺序 打印验证 int sum = 0; for(int i=0;i<nums.length;i++){ sum+=nums[i]; } if(sum%2!=0){ return false; } int half = sum/2; int[] dp = new int[half+1]; for(int i=1;i<nums.length;i++){ for(int j=half;j>0;j--){ if(j>=nums[i]) dp[j] = Math.max(dp[j],dp[j-nums[i]]+nums[i]); } } if(dp[half] == half){ return true; } else { return false; } } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
01背包组合问题
如果让你求的是一个组合的情况怎么办，比如：
给你一个整数数组 nums 和一个整数 target 。
向数组中的每个整数前添加 ‘+’ 或 ‘-’ ，然后串联起所有整数，可以构造一个 表达式 ：
例如，nums = [2, 1] ，可以在 2 之前添加 ‘+’ ，在 1 之前添加 ‘-’ ，然后串联起来得到表达式 “+2-1” 。
返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。
示例 1：
输入：nums = [1,1,1,1,1], target = 3
输出：5
解释：一共有 5 种方法让最终目标和为 3 。
-1 + 1 + 1 + 1 + 1 = 3
+1 - 1 + 1 + 1 + 1 = 3
+1 + 1 - 1 + 1 + 1 = 3
+1 + 1 + 1 - 1 + 1 = 3
+1 + 1 + 1 + 1 - 1 = 3
首先你得看出来这个题可以转化为背包问题：
假设加法的总和为x，那么减法对应的总和就是sum - x。所以我们要求的是 x - (sum - x) = target -> x = (target + sum) / 2
此时问题就转化为，装满容量为x的背包，有几种方法
这次是让求满足要求的组合数，使用一维dp数组解决：
- dp[j] 表示：填满j（包括j）这么大容积的包，有dp[j]种方法
- dp[j] += dp[j - nums[i]]
- 本题我们应该初始化 dp[0] 为 1
- 先遍历物品，再倒序遍历背包
- 打印dp数组
为什么递推公式是这个：
只要搞到nums[i]，凑成dp[j]就有dp[j - nums[i]] 种方法。
例如：dp[j]，j 为5，
已经有一个1（nums[i]） 的话，有 dp[4]种方法 凑成 容量为5的背包。
已经有一个2（nums[i]） 的话，有 dp[3]种方法 凑成 容量为5的背包。
已经有一个3（nums[i]） 的话，有 dp[2]中方法 凑成 容量为5的背包
已经有一个4（nums[i]） 的话，有 dp[1]中方法 凑成 容量为5的背包
已经有一个5 （nums[i]）的话，有 dp[0]中方法 凑成 容量为5的背包
dp[j] += dp[j - nums[i]]是之前本列的所有值，加上现在的dp[j - nums[i]，因为每次都加上了之前的dp[j]
比如之前只有物品1，容量j dp[j],现在多了物品2，那么所有情况就是 dp[j] = 之前只用物品1填满的 + 放入物品2后的，也就是dp[j] =dpj+dp[j - nums[i]]
组合问题记得初始化 dp[0] 因为跟计算价值不一样，如果dp[0]没有值，那么后面的数也都没有值
class Solution { // 背包问题求组合型 // 设 x是正数部分，sum-x是负数部分 2x-sum = target ; x = (target+sum)/2 // 递推公式： dp[j]+=dp[j-nums[i]] // 怎么装能 装满x，有几种方法 public int findTargetSumWays(int[] nums, int target) { if(nums == null || nums.length == 0 ){ return 0; } int sum =0; for(int i=0;i<nums.length;i++){ sum+=nums[i]; } // 如果正数部分向下取整了，那就不可能，因为正数部分不可能是小数 if((target+sum)%2 ==1){ return 0; } int x = (target+sum)/2; // 如果总和的绝对值都比不过目标值，那就不可能 if(Math.abs(sum) < Math.abs(target)){ return 0; } // 装满容量为x的背包，有多少种方法 int[] dp = new int[x+1]; dp[0] =1 ; for(int i=0;i<nums.length;i++){ for(int j=x;j>=nums[i];j--){ dp[j]+=dp[j-nums[i]]; } } return dp[x]; } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
01背包二维物品
有的时候物品维度有可能是二维的：
给你一个二进制字符串数组 strs 和两个整数 m 和 n 。
请你找出并返回 strs 的最大子集的长度，该子集中 最多 有 m 个 0 和 n 个 1 。
如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 。
示例 1：
输入：strs = [“10”, “0001”, “111001”, “1”, “0”], m = 5, n = 3
输出：4
解释：最多有 5 个 0 和 3 个 1 的最大子集是 {“10”,“0001”,“1”,“0”} ，因此答案是 4 。
其他满足题意但较小的子集包括 {“0001”,“1”} 和 {“10”,“1”,“0”} 。{“111001”} 不满足题意，因为它含 4 个 1 ，大于 n 的值 3 。
主要是要想到本题 用二维数组分别放 m和n的容量，那么循环就要循环三次，先物品，再倒叙循环两个背包：必须倒序，因为这个二维数组没有物品这个纬度，和之前的一维数组一样。
class Solution { // 还是01背包，物品是二维的，所以要用二维循环来遍历物品 public int findMaxForm(String[] strs, int m, int n) { if(strs == null || strs.length == 0){ return 0; } int[][] dp = new int[m+1][n+1]; // 最多放m个0，n个1，能最多放的子集数 for(String s:strs){ // 遍历物品 int oneCount = 0; int zeroCount = 0; for(char c:s.toCharArray()){ if(c == '0'){ zeroCount++; } else { oneCount++; } } for(int i=m;i>=zeroCount;i--){ for(int j=n;j>=oneCount;j--){ dp[i][j] = Math.max(dp[i][j],dp[i-zeroCount][j-oneCount]+1); } } } return dp[m][n]; } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
完全背包
完全背包和01背包的区别就是一个物品可以装多次，和01背包的区别就是遍历背包的时候不是逆序而是正序：
// 先遍历物品，再遍历背包
for(int i = 0; i < weight.size(); i++) { // 遍历物品
for(int j = weight[i]; j <= bagWeight ; j++) { // 遍历背包容量
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
}
}
- 1
- 2
- 3
- 4
- 5
- 6
正序遍历意味着使用的是本个物品已经更新过的dp值了，所以有添加多次的效果。
完全背包组合问题
给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。
请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。
假设每一种面额的硬币有无限个。
题目数据保证结果符合 32 位带符号整数。
示例 1：
输入：amount = 5, coins = [1, 2, 5]
输出：4
解释：有四种方式可以凑成总金额：
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1
递推公式和01背包组合问题一样，只是背包要正序遍历了：
class Solution { // 完全背包的组合问题 public int change(int amount, int[] coins) { if(coins == null || coins.length == 0){ return 0; } int[] dp = new int[amount+1]; // 有几种方式可以凑总金额为数组下标值的 dp[0] = 1; for(int i=0;i<coins.length;i++){ for(int j=coins[i];j<=amount;j++){ dp[j]+=dp[j-coins[i]]; } } return dp[amount]; } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
完全背包排列问题
给你一个由 不同 整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。
题目数据保证答案符合 32 位整数范围。
示例 1：
输入：nums = [1,2,3], target = 4
输出：7
解释：
所有可能的组合为：
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
请注意，顺序不同的序列被视作不同的组合。
排列问题和组合问题的递推公式相同，只是遍历顺序相反，需要先遍历背包再遍历物品
class Solution { public int combinationSum4(int[] nums, int target) { // 完全背包排列问题 if(nums ==null){ return 0; } int[] dp = new int[target+1]; dp[0] = 1; for(int j=1;j<=target;j++){ for(int i=0;i<nums.length;i++){ if(j>=nums[i]) dp[j]+=dp[j-nums[i]]; } } return dp[target]; } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
完全背包求最小值
给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。
你可以认为每种硬币的数量是无限的。
示例 1：
输入：coins = [1, 2, 5], amount = 11
输出：3
解释：11 = 5 + 5 + 1
求最小值提醒要注意的就是初始化，初始化的时候要把dp数组设置成int的最大值，但是dp[0]要为0，要不结果就全是最大值了
class Solution { public int coinChange(int[] coins, int amount) { if(coins ==null){ return 0; } int[] dp = new int[amount+1]; // 装满amount容量所需最少的硬币数 for(int i=1;i<dp.length;i++){ dp[i] = Integer.MAX_VALUE-1; } for(int i=0;i<coins.length;i++){ for(int j=coins[i];j<=amount;j++){ dp[j] = Math.min(dp[j],dp[j-coins[i]]+1); } } return dp[amount] == Integer.MAX_VALUE-1? -1:dp[amount]; // 没找到返回-1 } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
完全背包布尔型
- 单词拆分
给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。
注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。
示例 1：
输入: s = “leetcode”, wordDict = [“leet”, “code”]
输出: true
解释: 返回 true 因为 “leetcode” 可以由 “leet” 和 “code” 拼接成。
这道题目也不完全是完全背包类型，因为遍历物品并不是遍历的字符数组，而是遍历字符串s的一部分
class Solution { public boolean wordBreak(String s, List<String> wordDict) { // 类似于完全背包排列问题 boolean型 背包是s，物品是数组 boolean[] dp = new boolean[s.length()+1]; // 字符串长度为i时，判断可不可以由词典组成 HashSet<String> set = new HashSet<>(wordDict); dp[0] = true; // 0这里视为空字符 不是第一个字符，因为要保留dp[0] 为true才有后面的值 for(int j=1;j<=s.length();j++){ // 背包 for(int i=0;i<j && !dp[j];i++){ // 物品 // substring是左闭右开型的 // 注意dp[i]这个i延后了一位，代表的是 0到i-1位能不能被词典组成，s.substring(i,j)代表i到j-1位能不能被组成，如果都可以那么这个长度为j的字符（0到j-1位都满足），就满足了 if(set.contains(s.substring(i,j)) && dp[i]){ dp[j] = true; } } } return dp[s.length()]; } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
子序列问题
在面试中 子序列问题倒是经常遇到，需要重视一下，还有股票问题，打家劫舍一起看图：
我发现子序列的一个规律：
求的是子序列（不连续）就是dp数组的含义就是从0到i，如果是连续的就是以i为结尾的连续子序列
在一个数组或字符串中求，dpi j可以表示数组的第i位，第j位，如果在两个里面求最好dp i j表示数组的第i-1位，j-1位，减少了初始化的麻烦
而且往往最终结果是在某一个dp值中的，不一定是最后一个。
难点就在于思考怎么设计dp数组，以及不同情况的递推公式
最长回文子串 hot100第5题
有个常出现的题，代码随想录里没有：
给你一个字符串 s，找到 s 中最长的回文子串。
如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。
示例 1：
输入：s = “babad”
输出：“bab”
解释：“aba” 同样是符合题意的答案。
比较好的方法：中心扩散法
遍历s，每个字符向左右两边扩散，有奇数偶数两个情况 start = i - (max-1)/2; 这个比较骚
class Solution { // 中心拓展法 public String longestPalindrome(String s) { int result = 0; int start = 0,end = 0; for(int i=0;i<s.length();i++){ int one = centerExpand(s,i,i); // 以i向左右扩散 int middle = centerExpand(s,i,i+1); // 以i和i+1向左右扩散 int max = Math.max(one,middle); if(max > end - start){ start = i - (max-1)/2; // 这个用到了一些技巧，可以自己试一试 end = i + max/2; } } return s.substring(start,end+1); } public int centerExpand(String s,int left,int right){ // 从这个点 统计回文串长度 while(left>=0 && right<s.length() && s.charAt(left) == s.charAt(right)){ left--; right++; } return right-left-1; } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
class Solution { // 动态规划法 public String longestPalindrome(String s) { int len = s.length(); if (len < 2) { return s; } int maxLen = 1; int begin = 0; // dp[i][j] 表示 s[i..j] 是否是回文串 boolean[][] dp = new boolean[len][len]; for(int i =0 ;i<len;i++){ dp[i][i] = true; } char[] charArray = s.toCharArray(); // 先遍历列，因为递推公式需要用到左下角的值 for(int j=1;j<len;j++){ for(int i = 0;i<j;i++){ if(charArray[i] != charArray[j]){ dp[i][j] = false; } else { // i j之间没有数或者只有一个数了 就是真 if(j-i<3){ dp[i][j] = true; } else { dp[i][j] = dp[i+1][j-1]; } } // 有新结果记录位置 if(dp[i][j] && j-i+1 > maxLen){ maxLen = j-i+1; begin = i; } } } return s.substring(begin,begin+maxLen); } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
子序列（不连续）
给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
示例 1：
输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。
dp[i]表示i之前包括i的以nums[i]结尾的最长递增子序列的长度
遍历i的时候，要遍历0到i之前的每个，找到最大的连续子序列，然后加1就是dp[i]
为什么一定表示 “以nums[i]结尾的最长递增子序” ，因为我们在 做 递增比较的时候，如果比较 nums[j] 和 nums[i] 的大小，那么两个递增子序列一定分别以nums[j]为结尾 和 nums[i]为结尾， 要不然这个比较就没有意义了，不是尾部元素的比较那么 如何算递增呢。
dp是必须以i为结尾的，所以要记录最大值，因为最后一个字符结尾的不一定是最大的
class Solution { public int lengthOfLIS(int[] nums) { if(nums == null || nums.length ==0){ return 0; } int[] dp = new int[nums.length]; // dp[i]表示i之前包括i的以nums[i]结尾的最长递增子序列的长度 // 第i个数和第j个数比较，如果比j大，那么i的最长自增子序列就是j的加1，当然j的加1并不一定是i最长的，所以从0到i-1比较最大值 int maxResult = 1; for(int i=1;i<nums.length;i++){ for(int j=0;j<i;j++){ if(nums[i] > nums[j]) dp[i] = Math.max(dp[i],dp[j]+1); // max中的dp[i]为的就是在第二层循环中找最大值 } maxResult = Math.max(maxResult,dp[i]); } return maxResult; } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
子序列（连续）
给定一个未经排序的整数数组，找到最长且 连续递增的子序列，并返回该序列的长度。
连续递增的子序列 可以由两个下标 l 和 r（l < r）确定，如果对于每个 l <= i < r，都有 nums[i] < nums[i + 1] ，那么子序列 [nums[l], nums[l + 1], …, nums[r - 1], nums[r]] 就是连续递增子序列。
示例 1：
输入：nums = [1,3,5,4,7]
输出：3
解释：最长连续递增序列是 [1,3,5], 长度为3。
尽管 [1,3,5,7] 也是升序的子序列, 但它不是连续的，因为 5 和 7 在原数组里被 4 隔开。
dp[i]：以下标i为结尾的连续递增的子序列长度为dp[i]。
注意这里的定义，一定是以下标i为结尾，并不是说一定以下标0为起始位置。
本题只需要比较i和i的前一个位置就行了，比较简单
class Solution { public int findLengthOfLCIS(int[] nums) { if(nums == null || nums.length == 0){ return 0; } int[] dp = new int[nums.length]; // dp[i] 以nums[i]结尾的最长连续递增序列 int max = 1; for(int i=0;i<nums.length;i++){ dp[i] = 1; } // 1 3 5 4 7 // dp. 1 2 3 1 2 // 1 2 3 0 for(int i=1;i<nums.length;i++){ if(nums[i]>nums[i-1]){ dp[i] = dp[i-1]+1; // 传递当前最大 } max= Math.max(max,dp[i]); // 传递历史最大 } return max; } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
最长公共子序列
给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。
一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
例如，“ace” 是 “abcde” 的子序列，但 “aec” 不是 “abcde” 的子序列。
两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。
示例 1：
输入：text1 = “abcde”, text2 = “ace”
输出：3
解释：最长公共子序列是 “ace” ，它的长度为 3 。
dp[i][j]：长度为[0, i - 1]的字符串text1与长度为[0, j - 1]的字符串text2的最长公共子序列为dp[i][j]
有同学会问：为什么要定义长度为[0, i - 1]的字符串text1，定义为长度为[0, i]的字符串text1不香么？
这样定义是为了后面代码实现方便，如果非要定义为长度为[0, i]的字符串text1也可以,但是 需要初始化为0的情况，不太方便。
所以当求两个数组的公共最长子序列时，dp数组代表的最好是 i-1和j-1，因为是子序列，本题代表的是从0开始。。
class Solution { public int longestCommonSubsequence(String text1, String text2) { int[][] dp =new int[text1.length()+1][text2.length()+1]; // 长度为[0, i - 1]的字符串text1与长度为[0, j - 1]的字符串text2的最长公共子序列为dp[i][j] // dp[i][j] = Math.max(dp[i-1][j-1]) int result =0; for(int i =1;i<=text1.length();i++){ for(int j=1;j<=text2.length();j++){ if(text1.charAt(i-1) == text2.charAt(j-1)){ // 如果相同的话 abc abc 判断两个c的时候，是不是应该在 ab 和 ab 的基础上加1 啊 dp[i][j] = dp[i-1][j-1]+1; } else { // 如果不相同的话，如abc 和 ace 判断 c和e的时候，c和e已经不相同了，那么就判断 abc和ac 或者ab和ace看谁最大，大的不就是 最长的公共子序列吗 dp[i][j] = Math.max(dp[i][j-1],dp[i-1][j]); } } } return dp[text1.length()][text2.length()]; } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
