LeetCode 62题回溯与动态规划
来源：9-3 发现重叠子问题 Integer Break
软件工程小白菜
2019-04-02
波波老师您好，在9.3小节您曾经说过，如果理解了动态规划，62题Unique Paths就是一道简单的题目。
问题是：根据之前的学习来看，62题并没有符合最优子结构这个特征（并没有求什么最大最小值），为什么可以使用动态规划呢？换句话来说，第62题其实就是一个遍历寻找解的过程，难道不是只用递归回溯法就可以解决的吗？
请老师再解释一下，谢谢！
1回答
-
首先，强烈建议你先自己使用自己的递归回溯的思路实现一下。然后，根据自己实现的递归回溯算法，仔细思考一下，看看有没有重叠子问题？
至于最优子结构。是的，没有。因为这个问题根本不是一个最优化问题，所以谈不上最优子结构。所谓的最优子结构，是我们要能通过更小的问题的“最优解”，正确推导出更大的问题的“最优解”。但是对于这个问题，问题本身就是：到某个位置有多少步。所以，我们根本不需要找最优解，因为解只有一个。这也正是这个问题简单的地方——我们不需要顾及最优解的问题：）
以下为答案：
==========
这里的关键在于，这个机器人只能向下走或者向右走。所以，机器人来到一个格子，只能或者从上面下来，或者从左边过来，两种方式。所以，机器人到x，y位置的方式数，就等于到x - 1, y的方式数，加上到x, y - 1的方式数。
于是，我们就有转移方程：
dp[x][y] = dp[x - 1][y] + dp[x][y - 1]
基本条件就是，如果x == 0或者y == 0，只有一种方式可以走。
我的参考代码：
记忆化搜索：https://github.com/liuyubobobo/Play-Leetcode/blob/master/0062-Unique-Paths/cpp-0062/main.cpp
动态规划：https://github.com/liuyubobobo/Play-Leetcode/blob/master/0062-Unique-Paths/cpp-0062/main2.cpp
加油！：）
212019-04-03
相似问题