用动态规划求两个序列 s1s_1s1 和 s2s_2s2 的最长公共子序列长度,若 dp[i][j] 表示 s1s_1s1 前 i 个元素与 s2s_2s2 前 j 个元素的 LCS 长度。当 s1[i−1]=s2[j−1]s_1[i-1] = s_2[j-1]s1[i−1]=s2[j−1] 时,正确的状态转移是( )。
dp[i][j]
i
j
dp[i][j] = dp[i - 1][j - 1] + 1
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
dp[i][j] = dp[i - 1][j] + 1
dp[i][j] = dp[i][j - 1]