Leetcode62.不同路径
一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish” )。
问总共有多少条不同的路径?
(动态规划) $O(n \ast m ) $
很标准的动态规划,最上面一行只能横着走过去,最左边只能竖着,其余格子只能上面或者左面,那么就是F[i][j]=F[i − 1][j] +F[i][j - 1];
C++ 代码
class Solution {
public:
int uniquePaths(int m, int n) {
int A[105][105];
A[1][1] = 0;
for(int i = 1;i <= m;i ++) A[i][1] = 1;
for(int i = 1;i <= n;i ++) A[1][i] = 1;
for (int i = 2; i <= m; i++) {
for (int j = 2; j <= n; j++) {
A[i][j] = A[i - 1][j] + A[i][j - 1];
}
}
return A[m][n];
}
};