前言
本期我们来解决动规的经典题型------ 子数组问题
我们还是会使用动规五部曲来解决问题,下面我们仍然列出动规五部曲
1.明确dp数组含义
2.明确dp数组如何推导-递推公式
3.初始化dp数组
4.确定遍历顺序
5.打印dp数组排错
LeetCode T300 最长递增子序列
题目链接:300. 最长递增子序列 - 力扣（LeetCode）
题目思路:
1.明确dp数组含义
这里的dp[i]表示的是以dp[i]为结尾的最长递增子序列的长度
2.明确dp数组如何推导-递推公式
我们知道这里的递增不要求连续,只需要位置在i前面即可,所以我们定义一个j来遍历i前面的元素,这里dp[i]就等于dp[j]+1或者本身或者是dp[j]+1之间的最大值,因为在这个期间我们可以不断的更新dp[i]
3.初始化dp数组
初始化全为1即可
由于单个字母也构成递增子序列,所以长度为1
4.确定遍历顺序
顺序遍历,因为后面的dp值是由前面的推出来的
5.打印dp数组排错
题目代码:
class Solution { public int lengthOfLIS(int[] nums) { int[] dp = new int[nums.length]; int res = 1; Arrays.fill(dp, 1); for (int i = 1; i < dp.length; i++) { for (int j = 0; j < i; j++) { if (nums[i] > nums[j]) { dp[i] = Math.max(dp[i], dp[j] + 1); } res = Math.max(res, dp[i]); } } return res; } }
LeetCode T674 最长连续递增序列
题目链接:674. 最长连续递增序列 - 力扣（LeetCode）
题目思路:
1.明确dp数组含义
dp[i]表示i为结尾元素的最长连续子数组
2.明确dp数组如何推导-递推公式
dp[i]这里只能由前面一个元素推出来,所以dp[i] = dp[i-1]+1
3.初始化dp数组
仍然初始化为1
4.确定遍历顺序
顺序遍历即可
5.打印dp数组排错
题目代码:
class Solution { public int findLengthOfLCIS(int[] nums) { int[] dp = new int[nums.length]; int res = 1; Arrays.fill(dp, 1); for (int i = 1; i < dp.length; i++) { if (nums[i] > nums[i-1]) { dp[i] = dp[i-1] + 1; } res = Math.max(res, dp[i]); } return res; } }
LeetCode T718 最长重复子数组
题目链接:718. 最长重复子数组 - 力扣（LeetCode）
题目思路:
1.明确dp数组含义
dp[i][j] ：以下标i - 1为结尾的A，和以下标j - 1为结尾的B，最长重复子数组长度为dp[i][j]。 （特别注意： “以下标i - 1为结尾的A” 标明一定是 以A[i-1]为结尾的字符串 ）
至于为什么是i-1和j-1我会在最后给出解答
2.明确dp数组如何推导-递推公式
dp[i][j] = dp[i-1][j-1] + 1;
为啥是i-1和j-1呢?为啥不是别的呢,我在这里举个例子大家就能理解
假设nums1 = [1,2,3,2,1]
nums2 = [3,2,1,4,7]
我们这里匹配到i = 4,j=2 他们的前一个状态是两者同时向前一个单位,是同时回退
3.初始化dp数组
dp[i][0]和dp[0][j]都是无意义的,全部初始化为0即可,其他的随便初始化为啥都可以,因为在遍历的过程中会被覆盖的
4.确定遍历顺序
先遍历哪个都行,顺序遍历,因为右下角的元素依赖于左上角元素产生
5.打印dp数组排错
注:这里的dp[i][j]并不是答案,答案在数组中出现,因为这里dp数组的含义是以i-1和j-1结尾的数组a和数组b的最大公共子数组,这里i-1和j-1不一定是最后的结尾位置.
这里dp数组的定义为啥不用i和j呢?
我们思考这样一个问题,如果dp[i][j]定义为以i结尾和以j结尾,那么这里的dp[i][0]就需要遍历一遍数组a,[0][j]需要遍历一遍数组b,这样代码显得冗余了.
题目代码:
class Solution { public int findLength(int[] nums1, int[] nums2) { int[][] dp = new int[nums1.length+1][nums2.length+1]; int res = 0; for(int i = 1;i<=nums1.length;i++){ for(int j = 1;j<=nums2.length;j++){ if(nums1[i-1] == nums2[j-1]) dp[i][j] = dp[i-1][j-1] + 1; res = Math.max(res,dp[i][j]); } } return res; } }
