题解 | #不同路径的数目(一)#

import java.util.*;


public class Solution {
    /**
     *
     * @param m int整型
     * @param n int整型
     * @return int整型
     */
    public int uniquePaths (int m, int n) {
        // write code here
        // 设出发点[0][0]   终点为[m-1][n-1]
        // 走一步，两种情况可以到达终点
        int [][] step = new int [m][n];
        if (m == 1 || n == 1) {
            return 1;
        }
        for (int i = 0; i < m; i++) {
            if ( i == 0) {
                for (int j = 0; j < n; j++) {
                    step[i][j] = 1;
                }
            } else {
                step[i][0] = 1;
                for (int j = 1; j < n; j++) {
                    step[i][j] = step[i - 1][j] + step[i][j - 1];
                }
            }

        }
        return step[m - 1][n - 1];

    }
}

理解题目意思就很简单，定义二维数组，第0行和第0列都为1种情况，然后其余的就是相邻两个格子的走法相加。

注意二维数组的长度就是m和n