今天在刷leetcode的时候，遇到这样一道题目。
大概就是说机器人从左上角走到右下角的终点，每次只能向右或者向下走一步，求所有可能的唯一路径共有多少条。最容易想到的应该就是用DFS或者BFS将所有可能的解进行枚举。
typedef pair<int, int> Pos;
void dfs(Pos p, Pos end, int *count) {
if (p.first <= end.first && p.second <= end.second) {
if (p == end) {
(*count)++;
} else {
p.first++; //向右走
dfs(p, end, count);
p.first--; //栈返回后恢复原来的坐标
p.second++; //向下走
dfs(p, end, count);
}
}
}
int unique_path(int m, int n) {
Pos begin(0, 0);
Pos end(m - 1, n - 1);
int count = 0;
dfs(begin, end, &count);
return count;
}
很遗憾，即使只是在23x12这样的地图上，也需要遍历将近两亿次。那有没有存在更优的解呢？答案是肯定的。
我们来仔细分析下，当机器人走到终点时，它的前一步要么是在1这个位置，要么就是2这个位置。
因此，我们得出一个重要的结论：
机器人走到终点的所有路径 = 机器人走到1位置的所有路径 +机器人走到２位置的所有路径。
同理如果要求走到1位置的所有路径，只要求它上面和左面的所有路径之和。
再来看当被划红线的小方块作为终点时，都只有一条唯一的路径。
很明显我们可以用动态规划来解决这个问题。经过上面的分析后，可以列出状态转义方程：
dp[0][j] = 1
dp[i][0] = 1
dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
代码如下：
class Solution {
public:
int uniquePaths(int m, int n) {
int dp[m][n];
for (int i = 0; i < m; i++) {
dp[i][0] = 1;
}
for (int j = 0; j < n; j++) {
dp[0][j] = 1;
}
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
return dp[m-1][n-1];
}
};
相比起上面的DFS算法，使用动态规划时间复杂度只需要O(m*n)。在求解最优化问题时，无非最常用的就是贪心和动态规划两种。在使用动态规划中，先对问题仔细分析，列出状态转移方程以及边界条件，接下来代码就是水到渠成的事情了。
