2

问题定义：

给定两个长度相等的字符串 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]);
  }
}

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

4

1 回答 1

2

This algorithm uses Dynamic Programming. The key point in understanding dynamic programming is to understand the recursive step which in this case is within the if-else statement. My understanding about the matrix of size (a.length+1) * (b.length +1) is that for a given element in the matrix dp[i +1, j +1] it represents that if the we only compare string a[0:i] and b[0:j] what will be the child of both a[0:i] and b[0:j] that has most characters.

So to understand the recursive step, let's look at the example of "HARRY" and "SALLY", say if I am on the step of calculating dp[5][5], in this case, I will be looking at the last character 'Y':

A. if a[4] and b[4] are equal, in this case "Y" = "Y", then i know the optimal solution is: 1) Find out what is the child of "HARR" and "SALL" that has most characters (let's say n characters) and then 2) add 1 to n.

B. if a[4] and b[4] are not equal, then the optimal solution is either Child of "HARR" and "SALLY" or Child of "HARRY" and "SALL" which will translate to Max(dp[i+1][j] and dp[i][j+1]) in the code.

于 2013-06-10T14:48:42.780 回答