LeetCode|LeetCode1143. 最长公共子序列动态规划|leetcode

思路动规五部曲
1.定义dp数组
dp[i][j]表示第一个字符串前i-1个字符和第二个字符串中前j-1个字符中存在的最长公共子序列为dp[i][j]。如果定义为i的话就会很遍历和初始化的时候会很麻烦。
2.递推公式
如果小标为i和j的字符相等则dp[i][j]=dp[i-1][j-1]+1
如果不相等则dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1])

if(a==b){ dp[i][j]=dp[i-1][j-1]+1; }else{ dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]); }

3.初始化
根据递推公式和定义可以知道应该初始化为0.那就直接用默认值不初始化即可。
4.遍历顺序
根据递推公式，可以知道是正序遍历。
5.打印顺序
【LeetCode|LeetCode1143. 最长公共子序列】dp数组中最大的就是最后的结果。
代码

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