62. Unique Paths

问题

这个问题是说，有一个网格，从左下角走到右下角，每次只能向右或者向下走一步，问总共有多少种走法到右下角。

解析

我的思路是 我们从终点去分析这个题目。要想达到终点grid[m-1][n-1]，可以从上面到达，也可以从左边到达，那么到达终点的方式就是grid[m - 2][n-1] + grid[m-1][n-2]，从上面的走的结果加上从左边走的结果。同理到达上面和左边的两个格子的结果依然可以那么计算，这个地方就能找到子问题模式。每个格子都来自于他的左边和上边的结果。

那么我们自底向上从头遍历每个格子计算它的结果，到终点就可以计算出到他的结果了。

这个题目的pattern其实有点像爬楼梯。

这个题目是动态规划的网格问题。状态转移公式是dp[i][j] = dp[i-1][j] + dp[i][j-1],，根据前文的对于每个格子的结果是怎么来的的描述；然后初始化可以看最左边的一列只能从上面走来，所以只能有一种方式到达，同样的，最上面的一列也是只能从左边走来，也是只能有一种方式。

代码

class Solution {
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];
        for (int i = 0; i < m; i++) {
            dp[i][0] = 1;
        }
        
        for (int i = 0; i < n; i++) {
            dp[0][i] = 1;
        }
        
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        
        return dp[m - 1][n - 1];
    }
}

1. Unique Paths

Problem

This problem says that there is a grid that goes from the bottom left corner to the bottom right corner, and only one step at a time can be taken to the right or down, so ask how many ways there are to go to the bottom right corner in total.

! img

Solution

My idea is that we analyze this question from the end point. To reach the end point grid[m-1][n-1], you can either reach it from above or from the left, so the way to reach the end point is grid[m - 2][n-1] + grid[m-1][n-2], the result of the walk from above plus the result of the walk from the left. Similarly the result of reaching the two grids above and to the left can still be calculated then, and this is where the subproblem pattern can be found. Each grid comes from the results of his left and top.

Then we traverse each lattice from the bottom up to calculate its result to the end to calculate to his result.

The pattern of this topic is actually a bit like climbing stairs.

This topic is a dynamic programming lattice problem. The state transfer formula is dp[i][j] = dp[i-1][j] + dp[i][j-1], according to the previous description of how the result of each lattice comes; then the initialization can see that the leftmost column can only come from the top, so there can only be one way to reach it, and similarly, the top column can only come from the left, and there can only be one way.

Code

class Solution {
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];
        for (int i = 0; i < m; i++) {
            dp[i][0] = 1;
        }
        
        for (int i = 0; i < n; i++) {
            dp[0][i] = 1;
        }
        
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        
        return dp[m - 1][n - 1];
    }
}