https://leetcode-cn.com/problems/unique-paths/
一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish” )。
问总共有多少条不同的路径?
我的方法一:动态规划
步骤
- 确认状态
1.1 最后一步:到达第(m, n)点,或者从(m-1, n)过来,或者从(m, n-1)过来
1.2 子问题:f(m, n)可以转化为f(m-1, n)和(m, n-1)两个问题 - 转移方程
f(m, n) = f(m-1, n) + f(m, n-1) - 初始条件和边界条件
3.1 m>0, n>0
3.2 f(1, 1) = 1, f(*, 0) = 0, f(0, *) = 0 - 计算顺序
f(1, 1), f(1,2), f(2,1) f(m, n)
复杂度
时间复杂度:O(mxn)
空间复杂度:O(mxn)
代码
class Solution {
public:
int uniquePaths(int m, int n) {
if(m < 1 || n<1){
return 0;
}
int ** f = new int*[m+1];
for(int i = 0; i<=m; i++){
f[i] = new int[n+1];
for(int j = 0; j<=n; j++){
f[i][j] = 0;
}
}
f[1][1] = 1;
for(int i = 1; i<=m; i++){
for(int j = 1; j<=n; j++){
if(i>1 || j>1){
f[i][j] = f[i][j-1]+f[i-1][j];
}
}
}
int count = f[m][n];
for(int i = 0; i<=m; i++){
delete[] f[i];
f[i] = 0;
}
delete[] f;
f = 0;
return count;
}
};