LeetCode_114_UniquePaths

1. question: 不同路径（中等）

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

问总共有多少条不同的路径？

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/unique-paths

示例 1：

输入：m = 3, n = 7
输出：28

示例 2：

输入：m = 3, n = 2
输出：3
解释：
从左上角开始，总共有 3 条路径可以到达右下角。
1. 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右
3. 向下 -> 向右 -> 向下

示例 3：

输入：m = 7, n = 3
输出：28

示例 4：

输入：m = 3, n = 3
输出：6

提示：

1 <= m, n <= 100
题目数据保证答案小于等于 2 * 109

2. answers

这道题可以看成是动态规划的进阶题，和前面的爬楼梯明显不是一个等级的，将动态规划的递推公式，由一维变成了二维，不能仅靠两个变量来保存前面步骤的结果值。

同样，先逆推一下。每个位置都可由该位置的上面一个位置，和该位置的左边一个位置到达。因此，只需要获得该位置左侧位置的路径总和 和 该位置上面位置的路径总和，即可求得本位置的路径总和，即Path[m,n] = Path[m-1, n] + Path[m, n-1]。但是注意，下标一定是大于等于0的，即在正区间。对于[x, 0]的位置，只能由左边的位置到达；对于[0, x]的位置，只能由上面的位置到达。

另外，前面提到了，这是二维的位置，所以说，简单两个变量无法保存所需的值，需要设置一个二维数组保存。

public class Solution_0114 {

    public int uniquePaths(int m, int n) {

        // 定义数组，保存到达每个节点位置的对应的路径总和
        int[][] path = new int[m][n];

        // 初始化第一个节点。
        path[0][0] = 1;

        // 遍历每个节点，计算到达该节点的路径总和
        for (int i = 0; i < m; i++) {

            for (int j = 0; j < n; j++) {

                // 判断是否超出边界
                if(j - 1 >= 0 && i - 1 >= 0) path[i][j] = path[i - 1][j] + path[i][j-1];
                if(j - 1 >= 0 && i - 1 < 0) path[i][j] = path[i][j-1];
                if(j - 1 < 0 && i - 1 >= 0) path[i][j] = path[i - 1][j];
            }
        }

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

    public static void main(String[] args) {
        System.out.println();

        Solution_0114 s = new Solution_0114();

        System.out.println(s.uniquePaths(1, 1));
    }
}

3. 备注

参考力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台 (leetcode-cn.com)，代码随想录 (programmercarl.com)。