LeetCode 62 - Unique Paths

题干

有一个 m * n 的矩阵，有一个小机器人在左上角，它只能往下或往右走，问到达右下角一共有多少不同的路径？

思路

首先可以确定，一共要走 m + n 步。

要用动态规划的话，需要思考当前的状态，以及与上一个状态有什么关联？然后有了一个关系等式，问题就迎刃而解。

假设某一个状态，小机器人在 (i, j) 位置，此时走了 i + j 步。他的上一个位置可能在 (i - 1, j) 或者 (i, j - 1) 。那此时可能的不同路径数就是 (i - 1, j) 和 (i, j - 1) 处路径数之和。那关系就出来了：

dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

怎么走需要思考一下，因为除了原点，每个点都有很多不确定的路径。所以只能按照广度优先。

代码：

public int uniquePaths(int m, int n) {
    if (m == 0 || n == 0) {
        return 0;
    }
    if (m == 1 || n == 1) {
        return 1;
    }
    int[][] dp = new int[m][n];
    // 设定原点路径数为 1
    dp[0][0] = 1;
    // 广度优先遍历
    for (int step = 1; step <= m + n; step++) {
        int i = 0;
        int j = step - i;
        // 保证小机器人在矩阵内
        while (i < m && j >= 0) {            
            if (j < n) {
                if (i == 0) {
                    dp[i][j] = dp[i][j - 1];
                } else if (j == 0) {
                    dp[i][j] = dp[i - 1][j];
                } else {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                }              
            }
            i++;
            j = step - i;
        }
    }
    return dp[m - 1][n - 1];
}

题干
思路

LeetCode 62 - Unique Paths

题干

思路

FEATURED TAGS

FRIENDS