[LeetCode] 62. Unique Paths

正午 2020-01-06 PM 10℃ 0条

题目

一机器人在 m 列 n 行的网格的左上角,机器人每次只能向下或向右移动一个格子,移动到右下角的格子有多少条路径

请输入图片描述

上图是一个 7 列 3 行的示例图

注意: m 和 n 小于 100
例子1:

Input: m = 3, n = 2
Output: 3
Explanation:
From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:
1. Right -> Right -> Down
2. Right -> Down -> Right
3. Down -> Right -> Right

例子2:

Example 2:

Input: m = 7, n = 3
Output: 28

解法一

动态规划,因为机器人只能向下和向右移动,pathi 表示到第 i 列 j 行的点的步数,
path[i][j] = path[i][j-1] + path[i-1][j] 并且 path[0][j] = j, path[i][0] = i

代码实现如下:

class Solution {
public:
    int uniquePaths(int m, int n) {
        
        vector<vector<int>> path(m, vector<int>(n));
        for(int i=0; i<m; i++){
            path[i][0] = 1;
        }
        
        for(int i=0; i<n; i++){
            path[0][i] = 1;
        }
        
        for(int i=1; i< m; i++){
            for(int j=1; j< n; j++){
                path[i][j] = path[i-1][j] + path[i][j-1];
            }
        }
        return path[m-1][n-1];
    }
};

时间复杂度为 O(mxn)进一步优化空间复杂度

解法二

分析排列组合,直接求问题的最终解, 从 点 (0, 0) 走到点(m-1, n-1)总共 m+n-2 步, 其中 m-1 步向下, n-1 步向右,问题可以转为为有 m-1 个 “下”, n-1 个 ”右“, 排成一列有多少中排法。

标签: LeetCode

非特殊说明,本博所有文章均为博主原创。

评论