2021/1/25 求路径

题目描述

一个机器人在m×n大小的地图的左上角（起点）。
机器人每次向下或向右移动。机器人要到达地图的右下角（终点）。
可以有多少种不同的路径从起点走到终点？

备注：m和n小于等于100,并保证计算结果在int范围内

示例1

输入

2,1

返回值

1

示例2

输入

2,2

返回值

2

解题思路

1. 动态规划问题，将大任务拆分为小任务，每个小任务的目标与大任务一致，都是计算路径，只是规模缩小；
2. 从小任务可知，每一格会被走到的次数 = 上面一格的次数 + 左边一格的次数。从左上到右下遍历数组即可；
3. 因为只能往下或往右走，所以第一行和第一列只能为 1。

Java代码实现

public class Solution {
    /* 1. 二维数组解法 */
    public int uniquePaths (int m, int n) {
        int[][] dp = new int[m][n];
        // 初始化第一行和第一列为 1
        for (int i = 0; i < m; ++i) {
            dp[i][0] = 1;
        }
        for (int j = 0; j < n; ++j) {
            dp[0][j] = 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];
    }

    /* 2. 一维数组解法
        因为我们需要的最终结果在最后一行，所以可以用一维数组来代替二维数组每次遍历时的一维数组
    */
    public int uniquePaths (int m, int n) {
        // 在最左边 dp[0] 增加一个元素 0，保证每次第一个数 dp[1] = 1
        int[] dp = new int[n + 1];
        // 初始化第一行为 1，第一个元素为 0
        for (int i = 1; i < n + 1; ++i) {
            dp[i] = 1;
        }

        // 每一格的值 = 上面一格 + 左边一格
        for (int i = 1; i < m; ++i) {
            for (int j = 1; j < n + 1; ++j) {
                dp[j] = dp[j-1] + dp[j];
            }
        }
        return dp[n];
    }
}