题目链接
思路
分析动态规划题目的时候只需要考虑最后一个阶段,因为所有的阶段转化都是相同的,考虑最后一个阶段容易发现规律
在数组的动态规划问题中,一般 dp[i]
都是表示以 nums
以前 i 个元素组成(即 nums[i - 1]
)的状态;dp[i][j]
分别表示以 nums1
前 i 个元素(即 nums1[i - 1]
)组成和以 nums2
前 j 个元素(即 nums2[j - 1]
)组成的状态,以此类推
字符串也是个数组,是字符数组
表示状态
状态表示就是靠猜,但是会有猜的套路,一般都是通过最终结果和数组数量来猜
使用 \(dp[i][j]\) 表示 \(nums1\) 前 i 个元素和 \(nums2\) 前 j 个元素中最长的公共子序列长度
找状态转移方程
思考的方向是:大问题的最优解怎么由小问题的最优解得到
因为是找公共子序列,那么很显然要有判断字符是否相等的过程,那么我们可以分为两种情况讨论:
- \(s1[i]=s2[j]\) : \(dp[i][j]=dp[i−1][j−1]+1\)。代表必然使用 s1[i] 与 s2[j] 时 LCS 的长度。
- \(s1[i] \neq s2[j]\) : \(dp[i][j] = \max(dp[i - 1][j], dp[i][j - 1])\)。代表必然不使用 \(s1[i]\) (但可能使用 \(s2[j]\))和必然不使用 \(s2[j]\)(但可能使用 \(s1[i]\))时 LCS 的长度。
所以状态转移方程为:
\[dp[i][j] = \left\{ \begin{aligned} & dp[i - 1][j - 1] + 1, & s[i] = s[j], \\ & \max(dp[i - 1][j], dp[i][j - 1]), & s[i] \neq s[j]. \end{aligned} \right. \]边界处理
整个 dp
数组初始化为0
代码
dp
数组版
class Solution {
public int longestCommonSubsequence(String text1, String text2) {
int n1 = text1.length();
int n2 = text2.length();
int[][] dp = new int[n1 + 1][n2 + 1];
for(int i = 1; i <= n1; i++){
for(int j = 1; j <= n2; j++){
if(text1.charAt(i - 1) == text2.charAt(j - 1)){
dp[i][j] = dp[i - 1][j - 1] + 1;
}else{
// s1[i] != s2[j] 表示:必然不使用 s1[i] (但可能使用 s2[j])或者必然不使用 s2[j] (但可能使用 s1[i])
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
return dp[n1][n2];
}
}
标签:1143,int,s2,s1,DP,数组,序列,LeetCode,dp
From: https://www.cnblogs.com/shixuanliu/p/17343264.html