LeetCode·1143.最长公共子序列·动态规划
链接:https://leetcode.cn/problems/longest-common-subsequence/solution/-by-xun-ge-v-9wqe/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
题目
示例
思路
- 确定dp数组(dp table)以及下标的含义
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的处理上面,十分麻烦!!!
- 确定递推公式
主要就是两大情况: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]不相同,那就看看text1[0, i - 2]与text2[0, j - 1]的最长公共子序列 和 text1[0, i - 1]与text2[0, j - 2]的最长公共子序列,取最大的。
即:dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
代码如下:
if (text1[i - 1] == text2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}
- dp数组如何初始化
先看看dp[i][0]应该是多少呢?
test1[0, i-1]和空串的最长公共子序列自然是0,所以dp[i][0] = 0;
同理dp[0][j]也是0。
其他下标都是随着递推公式逐步覆盖,初始为多少都可以,那么就统一初始为0。
- 确定遍历顺序
从递推公式,可以看出,有三个方向可以推出dp[i][j]:
dp[i-1][j]
dp[i][j-1]
dp[i-1][j-1]
代码
#define MAX(a, b) ((a) > (b) ? (a) : (b))
int longestCommonSubsequence(char * text1, char * text2){
int len1 = strlen(text1);
int len2 = strlen(text2);
int dp[len1 + 1][len2 + 1];
int max = 0;
memset(dp, 0, sizeof(int) * (len1 + 1) * (len2 + 1));//定义比初始化
for(int i = 1; i <= len1; i++)
{
for(int j = 1; j <= len2; j++)//枚举两个数组元素
{
if(text1[i-1] == text2[j-1])//更新dp数组
{
dp[i][j] = MAX(dp[i][j], dp[i-1][j-1] + 1);
}
else
{
dp[i][j] = MAX(dp[i][j-1], dp[i-1][j]);//如果不相等就保存最大值,继承
}
max = MAX(max, dp[i][j]);
}
}
return max;
}
作者:xun-ge-v
链接:https://leetcode.cn/problems/longest-common-subsequence/solution/-by-xun-ge-v-9wqe/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
相关文章
- 【LeetCode】最长递增子序列的个数 [M](动态规划)
- 【LeetCode】递增的三元子序列 [M](动态规划)
- 【LeetCode】不同的子序列 II [H](动态规划)
- 【LeetCode】不同的子序列 [H](动态规划)
- 【LeetCode】最长回文子序列(动态规划)
- LeetCode——Best Time to Buy and Sell Stock II
- LeetCode_动态规划_中等_516.最长回文子序列
- LeetCode_优先级队列_回溯_659.分割数组为连续子序列
- LeetCode_素数筛_中等_204.计数质数
- LeetCode_二叉树_中等_106.从中序与后序遍历序列构造二叉树
- LeetCode_字符串_中等_6.Z 字形变换
- LeetCode·每日一题·2389. 和有限的最长子序列·贪心
- LeetCode·每日一题·1487. 保证文件名唯一·哈希
- LeetCode·每日一题·1805.字符串中不同整数的数目·哈希
- LeetCode·每日一题·面试题 01.09.字符串轮转·模拟
- LeetCode·392.判断子序列·动态规划
- LeetCode·71.简化路径·栈模拟
- LeetCode·每日一题·1403.非递增顺序的最小子序列·贪心
- LeetCode-104. 二叉树的最大深度(Goland实现)
- [LeetCode] 549. Binary Tree Longest Consecutive Sequence II 二叉树最长连续序列之 II
- [LeetCode] 202. Happy Number 快乐数
- [LeetCode] 80. Remove Duplicates from Sorted Array II 有序数组中去除重复项 II
- leetcode 105 从前序与中序遍历序列构造二叉树
- leetcode 144 145 94二叉树的三种递归遍历
- leetcode 344 反转字符串