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

作者：小小林熬夜学编程 | 2024-03-06 22:48:17

踩

最长公共子序列(lcs)(2) 动态规划

动态规划解最长公共子序列问题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);
    1
2
3
4
5

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小小林熬夜学编程/article/detail/201984