java - 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]; 
}

我们已经在第二个示例中将其作为内部循环。