leetcode 刷题day42动态规划Part11（1143.最长公共子序列、1035.不相交的线、53. 最大子序和、392.判断子序列）

1143.最长公共子序列

思路：718. 最长重复子数组两个数组对应相同且连续，所以递推公式是dp[i-1][j-1]+1。最长公共子序列不要求连续但要求相对顺序，差别主要在于递推公式。

对于该题主要有两大情况：text1[i - 1] 与 text2[j - 1]相同，text1[i - 1] 与 text2[j - 1]不相同。

• 如果text1[i - 1] 与 text2[j - 1]相同，那么找到了一个公共元素，所以dp[i][j] = dp[i - 1][j - 1] + 1;
• 如果text1[i - 1] 与 text2[j - 1]不相同，就取dp[i - 1][j]和dp[i][j - 1]最长公共子序列最大的。即：dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);

代码如下：

class Solution {public int longestCommonSubsequence(String text1, String text2) {char[] char1=text1.toCharArray();char[] char2=text2.toCharArray();int[][] dp=new int[char1.length+1][char2.length+1];for(int i=0;i<=char1.length;i++){dp[i][0]=0;}for(int j=0;j<=char2.length;j++){dp[0][j]=0;}for(int i=1;i<=char1.length;i++){for(int j=1;j<=char2.length;j++){if(char1[i-1]==char2[j-1]) dp[i][j]=dp[i-1][j-1]+1;else dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1]);}}return dp[char1.length][char2.length];}
}

1035.不相交的线

思路：这个题目乍一看没有思路，看完题解后发现该题等同于计算A和B的最长公共子序列（相对顺序不变）的长度。

所以解题代码和上一题完全相同，代码如下：

class Solution {public int maxUncrossedLines(int[] nums1, int[] nums2) {int[][] dp=new int[nums1.length+1][nums2.length+1];for(int i=0;i<=nums1.length;i++){dp[i][0]=0;}for(int j=0;j<=nums2.length;j++){dp[0][j]=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;else dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1]);}}return dp[nums1.length][nums2.length];}
}

53. 最大子序和

思路：使用贪心算法，记录累加和的最大值，且一旦累加和小于等于0则重新累加。

动规五部曲如下：

1、确定dp数组（dp table）以及下标的含义
dp[i]：包括下标i（以nums[i]为结尾）的最大连续子序列和为dp[i]。

2、确定递推公式
dp[i]有两个方向可以推出来：

• dp[i - 1] + nums[i]，即：nums[i]加入当前连续子序列和
• nums[i]，即：重新计算当前连续子序列和
  取最大的，所以dp[i] = max(dp[i - 1] + nums[i], nums[i]);

3、dp数组如何初始化
dp[i]依赖于dp[i - 1]的状态，dp[0]就是递推公式的基础。
dp[0]应为nums[0]即dp[0] = nums[0]。

4、确定遍历顺序
递推公式中dp[i]依赖于dp[i - 1]的状态，需要从前向后遍历。

5、举例推导dp数组

代码如下：

class Solution {public int maxSubArray(int[] nums) {int[] dp=new int[nums.length];int result=nums[0];dp[0]=nums[0];for(int i=1;i<nums.length;i++){dp[i]=Math.max(dp[i-1]+nums[i],nums[i]);if(result<dp[i]) result=dp[i];}return result;}
}

392.判断子序列

双指针解法：

class Solution {public boolean isSubsequence(String s, String t) {if(s.length()==0) return true;char[] charS=s.toCharArray();char[] charT=t.toCharArray();int i=0;for(int j=0;j<charT.length;j++){if(i==charS.length) break;if(charS[i]==charT[j]) i++;}if(i==charS.length) return true;else return false;}
}

这道题是编辑距离的入门题目，只需要计算删除的情况，不用考虑增加和替换的情况。掌握本题的动态规划解法是对后面要讲解的编辑距离的题目打下基础。

动态规划五部曲分析如下：

1、确定dp数组（dp table）以及下标的含义
dp[i][j] 表示以下标i-1为结尾的字符串s，和以下标j-1为结尾的字符串t，相同子序列的长度为dp[i][j]。

2、确定递推公式
在确定递推公式的时候，if (s[i - 1] != t[j - 1])，相当于t要删除元素，继续匹配。if (s[i - 1] == t[j - 1])，那么dp[i][j] = dp[i - 1][j - 1] + 1;，if (s[i - 1] != t[j - 1])，此时相当于t要删除元素，把当前元素t[j - 1]删除，那么dp[i][j] 的数值就是看s[i - 1]与 t[j - 2]的比较结果，即：dp[i][j] = dp[i][j - 1];
（这里不是很懂，需要多思考一下）

3、dp数组如何初始化
从递推公式可以看出dp[i][j]都是依赖于dp[i - 1][j - 1] 和 dp[i][j - 1]，所以dp[0][0]和dp[i][0]是一定要初始化的。

4、确定遍历顺序
dp[i][j]依赖于dp[i - 1][j - 1] 和 dp[i][j - 1]，遍历顺序应该是从上到下，从左到右。

5、举例推导dp数组

代码如下：

class Solution {public boolean isSubsequence(String s, String t) {int[][] dp=new int[s.length()+1][t.length()+1];for(int i=1;i<=s.length();i++){for(int j=1;j<=t.length();j++){if(s.charAt(i-1)==t.charAt(j-1)) dp[i][j]=dp[i-1][j-1]+1;else dp[i][j]=dp[i][j-1];}}if(dp[s.length()][t.length()]==s.length()) return true;else return false;}
}