从mXn矩阵的左上角到右下角的所有可能路径

Question

我正在经历this leetcode problem for going from top left to bottom right.

有多少可能的独特路径？

通过存储每个索引的结果，我能够理解这种动态编程方法。

  public int uniquePaths(int m, int n) {   
        int count[][] = new int[m][n]; 
        for (int i = 0; i < m; i++) 
            count[i][0] = 1; 
        for (int j = 0; j < n; j++) 
            count[0][j] = 1; 
        for (int i = 1; i < m; i++)  { 
            for (int j = 1; j < n; j++) {
                count[i][j] = count[i-1][j] + count[i][j-1]; //+ count[i-1][j-1]; 
            }
        } 
        return count[m-1][n-1];       
        // if (m == 1 || n == 1)  return 1;    
        // return  uniquePaths(m-1, n) + uniquePaths(m, n-1); 
    }

但是，我找到了这个我无法理解的解决方案。

  public int uniquePaths(int m, int n) {   
         int[] dp = new int[n]; 
         dp[0] = 1; 

       for (int i = 0; i < m; i++) { 
         for (int j = 1; j < n; j++) { 
           dp[j] += dp[j - 1]; 
         } 
       } 
       return dp[n - 1]; 
    }

这是the link to the problem

有人可以解释第二个解决方案。

Answer 1

在您的第一个解决方案中，填充了整个矩阵，但您可以注意到每行在count[i][j] = count[i-1][j] + count[i][j-1]中仅使用一次。

所以你基本上可以在使用后丢弃它。第二种解决方案正是如此。我们只能使用一行来执行所有计算。

当我们填写它时，我们可以用count[0][j] = count[0][j] + count[0][j-1]代替代码，count[0][j] += count[0][j-1]基本上是

    for (int i = 0; i < m; i++) 
        count[i][0] = 1; 

。

注意

for (int j = 0; j < n; j++) 
   count[0][j] = 1; 

没用，我们总是覆盖那些细胞。

和

dp[0][0] = 1;
for (int j = 1; j < n; j++) { 
   dp[0][j] += dp[0][j - 1]; 
}

相当于

jth

我们已经在第二个例子中作为内循环。

Answer 2

基本上，在第二种解决方案中，我们通过利用用于保存前一行计算的空间来优化空间复杂性。因为，在计算当前行中的值之后，其在jth位置的值将仅被下一行中的dp[j] += dp[j - 1];位置中的值消耗。 所以，dp[j] = dp[j] + dp[j - 1] => dp value of jth column of current row = dp value at jth pos in prev row + dp value of j-1 th pos of current row => jth

这里，前一行的值jth列被当前行的qazxswpoi位置的值覆盖。 谢谢 ！