dp problem

Why in some dp problem, when we define the dp array, sometimes we define the length of array is (length + 1), but sometimes is (length).

Example such as Unique Paths (int[][] dp = new int[m][n];) and Edit distance(int[][] dp = new int[word1.length() + 1][word2.length() + 1];)

Any discussion is appreciated.

1. public class Solution {
   
2.     public int uniquePaths(int m, int n) {
   
3.         if(m == 0 || n == 0)
   
4.         {
   
5.             return 0;
   
6.         }
   
7.         
   
8.         if(m == 1 || n == 1)
   
9.         {
   
10.             return 1;
    
11.         }
    
12.         
    
13.         int[][] dp = new int[m][n];
    
14.         
    
15.         for(int i = 0; i < m; i++)
    
16.         {
    
17.             dp[i][0] = 1;
    
18.         }
    
19.         
    
20.         for(int j = 0; j < n; j++)
    
21.         {
    
22.             dp[0][j] = 1;
    
23.         }
    
24.         
    
25.         for(int i = 1; i < m; i++)
    
26.         {
    
27.             for(int j = 1; j < n; j++)
    
28.             {
    
29.                 dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
    
30.             }
    
31.         }
    
32.         return dp[m - 1][n - 1];
    
33.     }
    
34. }

复制代码

1. public class Solution {
   
2.     public int minDistance(String word1, String word2) {
   
3.         int len1 = word1.length();
   
4.         int len2 = word2.length();
   
5.         
   
6.         int[][] dp = new int[word1.length() + 1][word2.length() + 1];
   
7.         
   
8.         for(int i = 0; i <= word1.length(); i++)
   
9.         {
   
10.             dp[i][0] = i;
    
11.         }
    
12.         
    
13.         for(int j = 0; j <= word2.length(); j++)
    
14.         {
    
15.             dp[0][j] = j;
    
16.         }
    
17.         
    
18.         for(int i = 0; i < word1.length(); i++)
    
19.         {
    
20.             for(int j = 0; j < word2.length(); j++)
    
21.             {
    
22.                 char c1 = word1.charAt(i);
    
23.                 char c2 = word2.charAt(j);
    
24.                 if(c1 == c2)
    
25.                 {
    
26.                     dp[i + 1][j + 1] = dp[i][j];
    
27.                 }
    
28.                 else
    
29.                 {
    
30.                     dp[i + 1][j + 1] = Math.min(Math.min(dp[i][j + 1] + 1, dp[i + 1][j] + 1), dp[i][j] + 1);
    
31.                 }
    
32.             }
    
33.         }
    
34.         return dp[len1][len2];
    
35.     }
    
36. }

复制代码

个人理解，这个要看dp的东西是什么含义，unique paths里面dp[i][j]就是坐标 i, j这个位置的情况，length * length就已经覆盖所有情况了；而edit distance里面，i，j可以理解为两个字符串分别到 i, j 位置的匹配情况，额外加一行一列，正好处理了两个string是 ""，即空字符串的情况。一般string的dp处理，都是用length + 1的。