动态规划解最长公共子序列问题LCS(二)

核心定义

​ 关于LCS使用动态规划求解的状态以及状态方程的定义在上文中已经做了介绍了，这里不再赘述。

求解

​ 对于需要输出所有LCS情况的要求，这里仅需要对上文中代码里的一些条件做修改即可。上文中仅能求解一种情况，主要原因在于比较dp[i - 1][j]与dp[i][j - 1]时，判断的条件没有单独列出等于的情况！要注意这点，我们可以从一张图中了解这个情况，图如下：

​ 有了这个认知，那做代码的修改也就比较容易了，具体代码如下：

int lcs(const char *str1, const char *str2) { int i, j; int str1_len = (int) strlen(str1); int str2_len = (int) strlen(str2); for (i = 0; i <= str1_len; ++i) { for (j = 0; j <= str2_len; ++j) { if (i == 0 || j == 0) { dp[i][j] = 0; } else if (str1[i - 1] == str2[j - 1]) { dp[i][j] = dp[i - 1][j - 1] + 1; } else { dp[i][j] = MAX(dp[i - 1][j], dp[i][j - 1]); } } } return dp[str1_len][str2_len]; } void get_lcs(const char *str1, const char *str2, int i, int j, string lcs) { while (i > 0 && j > 0) { if (str1[i - 1] == str2[j - 1]) { lcs.push_back(str1[i - 1]); --i; --j; } else { if (dp[i - 1][j] > dp[i][j - 1]) { --i; } else if (dp[i - 1][j] < dp[i][j - 1]) { --j; } else { get_lcs(str1, str2, i - 1, j, lcs); get_lcs(str1, str2, i, j - 1, lcs); return ; } } } reverse(lcs.begin(), lcs.end()); lcs_set.insert(lcs); }

​ 代码中使用了set做去重处理，注意这点。