这种题目一般是给两个字符串,找一些特性或进行一些操作。
根据题目意思设置二维数组,行列长度为两个字数组的长度加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]);
}
不同子序列:
这题base就是不考虑长子串的当前内容,往后看。dp[i-1][j].
如果长短数组当前元素相等就要还有加上dp[i-1][j-1]的情况的数量。
编辑距离:
有三种操作增删改,但其实增和删效果是一样的。
删除操作:
点击查看代码
if (word1[i - 1] == word2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1];
} else {
dp[i][j] = min(dp[i - 1][j] + 1, dp[i][j - 1] + 1);
}