3. dp 数组的大小设置

比如说后文 编辑距离问题，我首先讲的是自顶向下的递归解法，实现了这样一个 dp 函数：

int minDistance(String s1, String s2) {
    int m = s1.length(), n = s2.length();
    // 按照 dp 函数的定义，计算 s1 和 s2 的最小编辑距离
    return dp(s1, m - 1, s2, n - 1);
}
 
// 定义：s1[0..i] 和 s2[0..j] 的最小编辑距离是 dp(s1, i, s2, j)
int dp(String s1, int i, String s2, int j) {
    // 处理 base case
    if (i == -1) {
        return j + 1;
    }
    if (j == -1) {
        return i + 1;
    }
 
    // 进行状态转移
    if (s1.charAt(i) == s2.charAt(j)) {
        return dp(s1, i - 1, s2, j - 1);
    } else {
        return min(
            dp(s1, i, s2, j - 1) + 1,
            dp(s1, i - 1, s2, j) + 1,
            dp(s1, i - 1, s2, j - 1) + 1
        );
    }
}

然后改造成了自底向上的迭代解法：

int minDistance(String s1, String s2) {
    int m = s1.length(), n = s2.length();
    // 定义：s1[0..i] 和 s2[0..j] 的最小编辑距离是 dp[i+1][j+1]
    int[][] dp = new int[m + 1][n + 1];
    // 初始化 base case 
    for (int i = 1; i <= m; i++)
        dp[i][0] = i;
    for (int j = 1; j <= n; j++)
        dp[0][j] = j;
    
    // 自底向上求解
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            // 进行状态转移
            if (s1.charAt(i-1) == s2.charAt(j-1)) {
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                dp[i][j] = min(
                    dp[i - 1][j] + 1,
                    dp[i][j - 1] + 1,
                    dp[i - 1][j - 1] + 1
                );
            }
        }
    }
    // 按照 dp 数组的定义，存储 s1 和 s2 的最小编辑距离
    return dp[m][n];
}

这两种解法思路是完全相同的，但就有读者提问，为什么迭代解法中的 dp 数组初始化大小要设置为 int[m+1][n+1]？为什么 s1[0..i] 和 s2[0..j] 的最小编辑距离要存储在 dp[i+1][j+1] 中，有一位索引偏移？

能不能模仿 dp 函数的定义，把 dp 数组初始化为 int[m][n]，然后让 s1[0..i] 和 s2[0..j] 的最小编辑距离要存储在 dp[i][j] 中？

理论上，你怎么定义都可以，只要根据定义处理好 base case 就可以。

你看 dp 函数的定义，dp(s1, i, s2, j) 计算 s1[0..i] 和 s2[0..j] 的编辑距离，那么 i, j 等于 -1 时代表空串的 base case，所以函数开头处理了这两种特殊情况。

再看 dp 数组，你当然也可以定义 dp[i][j] 存储 s1[0..i] 和 s2[0..j] 的编辑距离，但问题是 base case 怎么搞？索引怎么能是 -1 呢？

所以我们把 dp 数组初始化为 int[m+1][n+1]，让索引整体偏移一位，把索引 0 留出来作为 base case 表示空串，然后定义 dp[i+1][j+1] 存储 s1[0..i] 和 s2[0..j] 的编辑距离。