1回答

liuyubobobo

2020-09-29

已采纳

不是根据问题选择，而是根据你定义的状态到底是什么而定，也就是根据你的逻辑而定。

实际上，对于 LCS 来说，定义成  int[m+1][n+1] 和定义成 int[m][n] 都是可以的。

如果定义成 int[m+1][n+1]，表示第一个字符串看了 i 个字符，第二个字符串看了 j 个字符。i 的取值范围是 [0, m] 一共 m + 1 个元素（可以一个字符都没有看）；同理，j 的取值范围是 [0, n] 共 n + 1 个元素。所以总的 dp 大小是 int[m+1][n+1]

如果定义成 int[m][n]，表示第一个字符串看到了索引为 i 的字符，第二个字符串看到了索引为 j 的字符。i 的取值范围是 [0, m - 1]， 一共 m 个元素（因为是索引，所以 i < m）；同理，j 的取值范围是 [0, n - 1] 共 n 个元素。所以总的 dp 大小是 int[m][n]

这两种定义方式，其实转台转移方程是一样的，区别是在初始值的设置上。我强烈建议你尝试使用这两种定义都做一遍这个问题，都是能通过的，体会一下不同状态的定义，对应的代码的细微不同（在有些情况下，不同状态的定义，对应的逻辑将完全不一样）。

请再回忆一下这个课程之前介绍二分查找，我也强调过这个问题，定义的变量语义不一样，我们的代码就会不一样。关键是我们自己的逻辑，而不是一定要这样或者那样。

P.S.

在定义成 dp[m + 1][n + 1] 的时候，根据上面的定义，dp[0][0] 的意思就是第一个字符串一个字符都没有看，第二个字符串也一个字符都没有看，此时是两个空串。

继续加油！：）

0

1

hh_lemontree

非常感谢！

2020-09-29

共1条回复