题目描述
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 3 x 7 grid. How many possible unique paths are there?
Note: m and n will be at most 100.
根据题意分析，我们得出一个重要的结论：
机器人走到终点的所有路径 = 机器人走到1位置的所有路径 +机器人走到２位置的所有路径。
同理如果要求走到1位置的所有路径，只要求它上面和左面的所有路径之和。
再来看当被划红线的小方块作为终点时，都只有一条唯一的路径。
很明显我们可以用动态规划来解决这个问题。经过上面的分析后，可以列出状态转义方程：
dp[][j] =
dp[i][] =
dp[i][j] = dp[i - ][j] + dp[i][j - ]
代码如下：
class Solution {
public:
int uniquePaths(int m, int n) {
int dp[m][n];
for (int i = ; i < m; i++) {
dp[i][] = ;
}
for (int j = ; j < n; j++) {
dp[][j] = ;
}
for (int i = ; i < m; i++) {
for (int j = ; j < n; j++) {
dp[i][j] = dp[i - ][j] + dp[i][j - ];
}
}
return dp[m-][n-];
}
};
使用动态规划时间复杂度只需要O(m*n)。在求解最优化问题时，无非最常用的就是贪心和动态规划两种。在使用动态规划中，先对问题仔细分析，列出状态转移方程以及边界条件，接下来代码就是水到渠成的事情了。