A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).
The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).
How many possible unique paths are there?
public class Solution { public int uniquePaths(int m, int n) { // Start typing your Java solution below // DO NOT write main() function if(m==1 || n==1) return 1; int[][] path = new int[m][n]; for(int i = 0 ;i < m; i++){ path[i][0] = 1; } for(int j = 0; j < n; j++){ path[0][j] = 1; } for(int i = 1;i < m; i++){//here is start from second step!!not the first one for(int j = 1; j< n; j++) { path[i][j] = path[i-1][j]+path[i][j-1]; } } return path[m-1][n-1]; } }
public class Solution { public int uniquePaths(int m, int n) { // Start typing your Java solution below // DO NOT write main() function int[][] path = new int[m][n]; for(int i = 0;i < m;i++){ for(int j =0; j < n;j++){ if(i==0 && j ==0) path[i][j] = 0; path[i][j] = (i>0?path[i-1][j]:0) + (j>0 ? path[i][j-1]:0); } } return path[m-1][n-1]; } }// not correct
public class Solution { public int uniquePaths(int m, int n) { if (m==0 || n==0) return 0; int[] dp = new int[n]; dp[0] = 1; for(int i=0;i<m;i++){ for(int j=1;j<n;j++){ if (i==0) dp[j] = 1; else dp[j] = dp[j] + dp[j-1]; } } return dp[n-1]; } }
learned: 有没有节省空间的方法呢？有的，观察上面程序可以发现循环是从上到下扫描行的，在每一行里，我们又是从左到右来扫描的，我们完全可以用一个滚动数组来表示每一行，算下一行的时候，只需要更新这个数组里的值便可以了。注意程序里的这一句 dp[j] = dp[j] + dp[j-1] 当我们复写这一层的dp[j]之前，dp[j]还是上一行的值，dp[j-1]是左边格子我们复写后的值，所以加起来等价于二维数组里面 dp[i][j] = dp[i-1][j] + dp[i][j-1]