木又连续日更第16天(16/138)
木又的第156篇leetcode解题报告
动态规划
类型第1篇解题报告
leetcode第62题:不同路径
https://leetcode-cn.com/problems/unique-paths/
【题目】
一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为“Start” )。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为“Finish”)。
问总共有多少条不同的路径?
示例 1:
输入: m = 3, n = 2
输出: 3
解释:
从左上角开始,总共有 3 条路径可以到达右下角。
1. 向右 -> 向右 -> 向下
2. 向右 -> 向下 -> 向右
3. 向下 -> 向右 -> 向右
示例 2:
输入: m = 7, n = 3
输出: 28
【思路】
本题当然可以用动态规划的思想,dp[i][j] = dp[i-1][j] + dp[i][j-1]
但是,本题是最简单的排列组合,相当于从m+n-2步中选择m-1步向下,其余步向右,答案是C (m-1, m+n-2) = m * (m+1) * … *(m+n-2) / 1 / 2 / … (n-1)
【代码】
python版本
class Solution(object):
def uniquePaths(self, m, n):
"""
:type m: int
:type n: int
:rtype: int
"""
# 总步数 m+n-2
# C (m-1, m+n-2)
res = 1
for i in range(m, m+n-1):
res *= i
for i in range(1, n):
res /= i
return res
C++版本
class Solution {
public:
int uniquePaths(int m, int n) {
// 总步数 m+n-2
// C (m-1, m+n-2)
double res = 1;
if(m < n)
m, n = n, m;
for(int i=m, j=1; i<m+n-1; i++, j++){
res *= i;
if(j < n)
res /= j;
}
return res;
}
};