从mXn矩阵的左上到右下的所有可能路径 [英] All possible paths from top left to bottom right of a mXn matrix

问题描述

我正在经历从左上角到右下角的这个leetcode问题.

有多少个可能的唯一路径?

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

  public int uniquePaths(int m，int n){int count [] [] =新的int [m] [n];对于(int i = 0; i< m; i ++)count [i] [0] = 1;对于(int j = 0; j< n; j ++)count [0] [j] = 1;对于(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];}}返回计数[m-1] [n-1]；//如果(m == 1 || n == 1)返回1；//返回uniquePaths(m-1，n)+ uniquePaths(m，n-1);} 

但是，我找到了我无法理解的解决方案.

  public int uniquePaths(int m，int n){int [] dp = new int [n];dp [0] = 1;对于(int i = 0; i< m; i ++){for(int j = 1; j< n; j ++){dp [j] + = dp [j-1];}}返回dp [n-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];} 

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

I was going through this leetcode problem for going from top left to bottom right.

How many possible unique paths are there?

I was able to understand this method of dynamic programming by storing the result for every index.

  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); 
    }

However, I found this solution which I am not able to understand.

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

Here is the link to the problem

Can somebody please explain the 2nd solution.

解决方案

In your first solution whole matrix is filled, but you can notice that each row is used only once in count[i][j] = count[i-1][j] + count[i][j-1].

So you can basically discard it after use. Second solution is doing exactly that. We can use only one row to perform all calculation.

When we fill it we can replace the code with count[0][j] = count[0][j] + count[0][j-1], which is basically count[0][j] += count[0][j-1].

Note that

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

is useless, we always overwrite those cells.

And

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

is equivalent to

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

which we already have as inner loop in second example.

这篇关于从mXn矩阵的左上到右下的所有可能路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！