Zeki's Blog
0%

不同路径

Posted on

不同路径

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

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

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

robot_maze

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

思路1: 递归, 当前节点到终点的路径数等于往右走和往左右的路径和.

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    int max = 0;
    public int uniquePaths(int m, int n) {
        find(m, n, 0, 0);
        return max;
    }

    public void find(int m, int n, int x, int y) {
        if(x >= m || y >= n) {
            return;
        }
        if(x == m - 1 && y == n - 1) {
            max++;
        }
        find(m, n, x + 1, y);
        find(m, n, x, y + 1);
    }
}

思路2: 思路1在leetcode中超时, 所以采用dp数组维护每个位置的路径数,终点位置只有一种.其余位置dp[i][j] = dp[i+1][j] + dp[i][j+1]

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];
        for(int row = m - 1; row >= 0; row--) {
            for(int column = n - 1; column >= 0; column--) {
                if(row == m - 1 && column == n - 1) {
                    dp[row][column] = 1;
                }else {
                    int down = 0;
                    if(row + 1 < m) {
                        down = dp[row+1][column];
                    }
                    int right = 0;
                    if(column + 1 < n) {
                        right = dp[row][column+1];
                    }
                    dp[row][column] = down + right;
                }


            }
        }
        return dp[0][0];
    }

}