常见字符串的算法解释

Question

问题定义:

给定两个长度相等的字符串 a 和 b，可以构造的最长字符串 (S) 是什么使得 S 是 a 和 b 的子字符串。如果 x 可以通过从 y 中删除 0 个或多个字符而形成，则称字符串 x 是字符串 y 的子字符串

输入格式

两个字符串 a 和 b，用换行符分隔它们

约束

所有字符都是大写的并且介于ascii值65-90之间字符串的最大长度是5000

输出格式

字符串S的长度

示例输入 #0

哈利莎莉

示例输出 #0

2

从HARRY和SALLY中删除零个或多个字符可能得到的最长可能字符子集是AY，其长度为2。

解决方法:

public class Solution {
  public static void main(String[] args) throws Exception {
    BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    char[] a = in.readLine().toCharArray();
    char[] b = in.readLine().toCharArray();
    int[][] dp = new int[a.length + 1][b.length + 1];
    dp[0][0] = 1;
    for (int i = 0; i < a.length; i++)
        for (int j = 0; j < b.length; j++)
           if (a[i] == b[j])
              dp[i + 1][j + 1] = dp[i][j] + 1;
           else
              dp[i + 1][j + 1] = Math.max(dp[i][j + 1], dp[i + 1][j]);
              System.out.println(dp[a.length][b.length]);
  }
}

有人遇到过这个问题并使用这样的解决方案解决了吗？我以不同的方式解决了它。只发现这个解决方案很优雅，但到目前为止还无法理解。谁能帮忙解释一下。

Answer 1

该算法使用Dynamic Programming .理解动态规划的关键点是理解递归步骤，在这种情况下，递归步骤在 if-else 语句中。我对大小矩阵 (a.length+1) * (b.length +1) 的理解是，对于矩阵中的给定元素 dp[i +1, j +1 ] 它表示如果我们只比较字符串 a[0:i] 和 b[0:j] 什么将是这两个 a[0:i] 和 b[0:j] 具有最多的字符。

为了理解递归步骤，让我们看一下“HARRY”和“SALLY”的例子，假设我在计算dp[5][5]的步骤，在这个在这种情况下，我将查看最后一个字符 'Y':

一个。如果 a[4] 和 b[4] 相等，在这种情况下 "Y"= "Y"，那么我知道最优解决方案是:1) 找出 "HARR" 和 "SALL" 中具有最多字符(比方说 n 个字符)的 child 是什么，然后 2) 添加 1 到 n。

B.如果 a[4] 和 b[4] 不相等，则最佳解决方案是 "HARR" 和 的 child "SALLY" 或 "HARRY" 和 "SALL" 的 child ，它将转换为 Max(dp[i+1][j] 和dp[i][j+1]) 在代码中。