动态规划----unique paths

悠悠 2022-05-23 09:04 134阅读 0赞

1、题目：

A robot is located at the top-left corner of a *m* x *n* grid (marked 'Start' in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).

How many possible unique paths are there?

Example 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

Example 2:

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

2、解答： f(n,m)只能从上或者左边走过来，因此f(n,m) = f(n-1,m) + f(n,m-1)。现在看起始条件，若n = 0 ,f(0,m) = 1,m=0,f(n,0) = 1

3、代码：

C++代码

class Solution {
    public:
        int uniquePaths(int m, int n) {
            int path[m][n]; 
            
            for(int i=0;i<m;i++)
                path[i][0] = 1;
            
            for(int j=0;j<n;j++)
                path[0][j] = 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];
        } 
    };

python代码

class Solution:
        def uniquePaths(self, m, n):
            """
            :type m: int
            :type n: int
            :rtype: int
            """
            path = [[1 for i in range(n)] for j in range(m)]
           
            for i in range(1,m):
                for j in range(1,n):
                    path[i][j] = path[i-1][j] + path[i][j-1]
            
            return path[-1][-1]

发表评论取消回复

表情：

评论列表（有 0 条评论，134人围观）

还没有评论，来说两句吧...

相关阅读

相关 leetcode 63. Unique Paths II DP动态规划

Follow up for “Unique Paths”: Now consider if some obstacles are added to the grids. Ho

爱被打了一巴掌/ 2022年06月09日 11:42/ 0 赞/ 199 阅读

相关 leetcode 62. Unique Paths DP动态规划

A robot is located at the top-left corner of a m x n grid (marked ‘Start’ in the diagram

我不是女神ヾ/ 2022年06月09日 11:39/ 0 赞/ 157 阅读

相关 [Leetcode][python]Unique Paths/Unique Paths II

Unique Paths 题目大意机器人从起点到终点有多少条不同的路径，只能向右或者向下走。解题思路动态规划由于只能有向下向右，只有从\[1\]

左手的ㄟ右手/ 2022年06月07日 07:13/ 0 赞/ 400 阅读

相关动态规划--unique paths 2

1、题目： A robot is located at the top-left corner of a m x n grid (marked 'Start' in the

刺骨的言语ヽ痛彻心扉/ 2022年05月23日 09:09/ 0 赞/ 181 阅读

相关动态规划----unique paths

1、题目： A robot is located at the top-left corner of a m x n grid (marked 'Start' in the

悠悠/ 2022年05月23日 09:04/ 0 赞/ 135 阅读

相关 Unique Paths（动态规划求解）

题目题目来源：[LeetCode][] 1. A robot is located at the top-left corner of a m x n grid (

Myth丶恋晨/ 2022年05月08日 02:42/ 0 赞/ 183 阅读

相关【Leetcode】62. Unique Paths(动态规划)

A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram

谁借莪１个温暖的怀抱￠/ 2022年03月01日 08:48/ 0 赞/ 193 阅读

相关【Leetcode】63. Unique Paths II（动态规划）

A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram

曾经终败给现在/ 2022年02月27日 10:24/ 0 赞/ 191 阅读

相关 unique-paths

/\\ \ \ @author gentleKay \ A robot is located at the top-left corner of a m x n g

怼烎@/ 2021年11月09日 08:36/ 0 赞/ 292 阅读

相关 Unique Paths

class Solution { public: int uniquePaths(int m, int n) { ass

悠悠/ 2021年10月23日 09:59/ 0 赞/ 291 阅读