[leetcode] 62. Unique Paths

[leetcode] 62. Unique Paths

Description

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?

Above is a 7 x 3 grid. How many possible unique paths are there?

Note: m and n will be at most 100.

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 -> Down2. Right -> Down -> Right3. Down -> Right -> Right

Example 2:

Input:

m = 7, n = 3

Output:

28

分析

题目的意思是：一个机器人从左上角走到右下角，有几种走法。

令dp[i][j]为从0，0位置到i，j位置的走法数，所以dp[i][j]=dp[i-1][j]+dp[i][j-1],即既可以从 左边的i-1,j位置走到i,j位置，也可以从i,j-1位置走到i,j位置。

代码

class Solution {public: int uniquePaths(int m, int n) { vector> dp(m,vector(n,1)); for(int i=1;i

参考文献

​​62. Unique Paths​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。