[字符串](http://10.160.111.129/p/2680?tid=68920b24c9d615d80a10e864)
问题:
-
当实现代码以后一定要检查:
- 边界是否都合适
- 索引用的是否正确
- 如果有预制小边界在提交代码时一定要放开
思路:
-
目的是找到字符串匹配的最大数量,或者不匹配的最小数量,可以通过动态规划实现,
-
递推公式:
以下递推公式注意下标的含义。第一个式子字符串从0开始,第二个式子对字符串进行了处理,从1开始。
-
寻找最小不匹配:
dp[i][j] = min(dp[i - 1][j] + (a[i - 1] != c[i + j - 1]), dp[i][j - 1] + (b[j - 1] != c[i + j - 1])); -
寻找最大匹配:
dp[i][j] = max(dp[i - 1][j] + (a[i] == c[i + j]), dp[i][j - 1] + (b[j] == c[i + j]));
-