62. Unique Paths

# medium

Using two-layer array to record paths for each grid start from right-down corner to left-up corner.

Solution:

1. Initilize down and left parts of the grid with number of 1

2. Compute down-up or left-right grid based on known grid. f(x,y) = f(x-1,y) + f(x,y-1)

Java(O(mn))

class Solution {
    public int uniquePaths(int m, int n) {
        int[][] paths = new int[m][n];
        for(int[] arr: paths)
            Arrays.fill(arr, 1);
        for(int i = 0; i < m; i ++)
            paths[i][0] = 1;
        
        for(int i = 1; i < m; i ++)
            for(int j = 1; j < n; j ++)
                paths[i][j] = paths[i-1][j] + paths[i][j-1];
        
        return paths[m-1][n-1];
    }
}

Python

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        paths = [[1] *n for i in range(m)]
        
        for i in range(1, m):
            for j in range(1, n):
                paths[i][j] = paths[i-1][j] + paths[i][j-1]
                
        return paths[-1][-1]

这道题思路简单，但是要一次性写对很难，因为要非常清楚index，很容易错，右下角index为（0，0）；并且事先一定要定义好array记录的意义，记录的不是每一格到终点的步数，而是每一格到终点的路径的个数。