LeetCode:62. 不同路径(python、c++)

题目描述

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

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

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

LeetCode:62. 不同路径(python、c++)

例如,上图是一个7 x 3 的网格。有多少可能的路径?

示例 1:

输入: m = 3, n = 2
输出: 3
解释:
从左上角开始,总共有 3 条路径可以到达右下角。

  1. 向右 -> 向右 -> 向下
  2. 向右 -> 向下 -> 向右
  3. 向下 -> 向右 -> 向右

示例 2:

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

提示:

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

题解
动态规划O(nm)
状态表示:
f[i][j]表示从起点[1, 1]走到点[i, j]的所有方案的集合
状态转移:
因为只能向左和向右走,所以可以右状态f[i - 1][j]和f[i][j - 1]转移过来
为了处理麻烦的边界问题,可以令下标从1开始,同时初始化,第一行每个点和每一列的方案数均为1,因为只能从起点向左或向右走得到。

c++版

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

python版

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        l = [[0 for _ in range(m)] for _ in range(n)]
        l[0][0] = 1;
        for i in range(n):
            for j in range(m):
                if not i and not j:
                    continue
                elif not i:
                    l[i][j] = l[i][j - 1]
                elif not j:
                    l[i][j] = l[i - 1][j]
                else:
                    l[i][j] = l[i - 1][j] + l[i][j - 1]
        return l[n-1][m-1]
匿名

发表评论

匿名网友