動規方程如下：
最長公共子串，由于匹配的字串必須在A、B串都是連續的，因此在更新dp[i][j]的時候只能從dp[i-1][j-1]。
//最長公共字串int longestCommonSubstring(string &A, string &B) { // write your code here size_t m = A.size(); size_t n = B.size(); int res = 0; vector<vector<int>> dp(m, vector<int>(n)); for (int i = 0; i < static_cast<int>(m); ++i) { for (int j = 0; j < static_cast<int>(n); ++j) { if (A[i] == B[j]) { if (i>0 && j>0) { dp[i][j] = dp[i - 1][j - 1] + 1; } else { dp[i][j] = 1; } } if (res < dp[i][j]) { res = dp[i][j]; } } } return res;}新聞熱點
疑難解答
