114. Unique Paths [by Java]

Description

A robot is located at the top-left corner of a m x n grid.

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.

How many possible unique paths are there?

m and n will be at most 100.

Example

Given m = 3 and n = 3, return 6.
Given m = 4 and n = 5, return 35.

题目如上，分析题目，从网格的最左上方的一个格子走到指定位置，问有多少种走法？区别于之前做的题目，之前的一道题目问的是最短路径，而这道问的是走法的种类。总的思路是不变的，动态规划嘛。两道题目共同点在于：在走的过程中，只能向右或者向下。有了这个限制条件，题目会变得容易很多。如图所示：

网格可以分为两个区域，如图中的红色和绿色，由于不能向左和向上走，所以前往“最左边”和“最右边”的格子（红色格子）只有一种走法。如果想要到达最上面一排的格子，只能向右，同理到达最左面的格子，只能向下。因为是二维的，所以想到可以用一个二维数组来表示到每个点的走法。值得注意的是，传入的参数m,n表示行列数，用数组表示后，右下角的格子为pace[m-1][n-1], 别手抖写成pace[m][n]，会越界的 - - (手动滑稽)

代码实现上，也是要分两类处理的，红色的，直接赋值1.  绿色的，要这样考虑，想要走到A号网格，就必须先走到B或者C，那么只要用走到B的方法总数加上走到C的方法总数，就是走到A的方法总数了，具体代码如下。如有错误，欢迎批评指正~

public class Solution {
    /**
     * @param m: positive integer (1 <= m <= 100)
     * @param n: positive integer (1 <= n <= 100)
     * @return: An integer
     */
    public int uniquePaths(int m, int n) {
        // write your code here
        int[][]pace=new int[m][n];
        for(int i=0;i<m;i++){
            pace[i][0]=1;
        }
        for(int j=0;j<n;j++){
            pace[0][j]=1;
        }
        for(int i=1;i<m;i++){
            for(int j=1;j<n;j++){
                pace[i][j]=pace[i-1][j]+pace[i][j-1];
            }
        }
        return pace[m-1][n-1];
    }
}

2018-05-24