动态规划-最长公共子串解释

Question

我是一个新手，正在努力研究动态编程，这对我来说似乎是个谜。我正在查看使用 DP 的最长公共子串问题的解决方案。其代码如下：-

int dp[N+1][N+1];

for (int i = 0; i <= N; ++i)

  dp[0][i] = dp[i][0] = 0;

for (int i = 1; i <= N; ++i)

  for (int j = 1; j <= N; ++j) {

    dp[i][j] = max(dp[i-1][j], dp[i][j-1]);

    if (A[i-1] == B[j-1])

      dp[i][j] = max(dp[i][j], dp[i-1][j-1]+1);

  }


int answer = dp[N][N];

它的解决方案看起来很简单，但我很难理解该解决方案。有人能解释一下代码中发生了什么吗？这如何解决 LCS 问题？

Answer 1

我建议您了解解决方案的总体思路。这里有一些参考，从最简单的解释到更深入的解释：

维基 - https://en.wikipedia.org/wiki/Longest_common_substring_problem
YouTube - https://www.youtube.com/watch?v=aSwu8Z9nzOg

以及您在上面介绍的有关此解决方案的学术参考资料：

然后，在了解他们的解决方案和他们解决这个问题的方法之后，你会发现你可以自己实现它或者完全理解你的算法中的逻辑

祝你好运！

动态规划-最长公共子串解释

Dynamic programming- Longest common substring explanation

c++

dynamic-programming