LeetCode 62题回溯与动态规划

Question

波波老师您好，在9.3小节您曾经说过，如果理解了动态规划，62题Unique Paths就是一道简单的题目。

问题是：根据之前的学习来看，62题并没有符合最优子结构这个特征（并没有求什么最大最小值），为什么可以使用动态规划呢？换句话来说，第62题其实就是一个遍历寻找解的过程，难道不是只用递归回溯法就可以解决的吗？

请老师再解释一下，谢谢！

Answer 1

liuyubobobo 2019-04-03 00:30:09

首先，强烈建议你先自己使用自己的递归回溯的思路实现一下。然后，根据自己实现的递归回溯算法，仔细思考一下，看看有没有重叠子问题？

至于最优子结构。是的，没有。因为这个问题根本不是一个最优化问题，所以谈不上最优子结构。所谓的最优子结构，是我们要能通过更小的问题的“最优解”，正确推导出更大的问题的“最优解”。但是对于这个问题，问题本身就是：到某个位置有多少步。所以，我们根本不需要找最优解，因为解只有一个。这也正是这个问题简单的地方——我们不需要顾及最优解的问题：）

以下为答案：

==========

这里的关键在于，这个机器人只能向下走或者向右走。所以，机器人来到一个格子，只能或者从上面下来，或者从左边过来，两种方式。所以，机器人到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

加油！：）

• 提问者 软件工程小白菜 #1

  多谢老师，我用递归回溯法实现了此问题，但LC给出了Time Limited Exceeded。通过老师的提示和自己的思考，确实发现了其中的重叠子问题，准备自己根据思路实现一遍再来看答案，多谢老师！