# 第 8 节超级重要的动态规划问题

# 「力扣」第 509 题：斐波拉契数列、第 70 题：爬楼梯

这两道问题是动态规划的入门问题。爬楼梯子问题之间的关系和斐波拉契数列是一模一样的。大家可以用「记忆化递归」和「递推」的方式都写一下，后面给出的问题可以只用「递推」实现。

描述清楚状态最重要，其它信息可以在在代码当中得到体现。

这是一道很经典的动态规划问题。定义子问题（状态）的时候需要考虑「偷」和「不偷」下标为 i 的房子。为了保证求解过程具有无后效性，将状态表格设计成二维，这件事情叫：子问题定义得更具体，子问题在之间的描述就越简单（这件事情没有那么绝对，大家不妨作为经验先接受它）。

什么叫子问题定义更具体呢？这个问题的表格是这样的：

子序列，每一个数字是否被选取，需要分类讨论。因此，在状态定义的时候，定义 dp[i] 表示：以 nums[i] 结尾的最长上升子序列的长度。在这样的定义下，nums[i] 必须被选择，这件事情保证了求解的过程满足「无后效性」。

这道问题也是被 liuyubobobo 老师推荐的一道问题，他特别强调了：最长上升子序列常见的解法有 2 种。的做法在网上已经有了充分的讨论。而这道题的二分查找算法，更本质上是因为 状态的定义发生了变化，使得复杂度降到了。因此我们需要深刻理解状态的定义，状态的定义非常关键。

是一道和「力扣」第 300 题类似的问题，连续子段的问题和子序列问题一样类似，有不确定的地方。因此，状态的定义中包含 nums[i] 必须被选择的信息，保证了求解过程具有无后效性。

这道题的动态规划解法，是我觉得最像填表法的。因为它的状态就是一张二维表格，填表的顺序还需要我们注意。

这些问题大家可以在题解区、讨论区找到它们的解法，真正理解状态涉及的思想（如何定义子问题），是最重要的。其它状态转移方程、初始化、填表顺序、输出都依赖于状态定义。

「力扣」上的有 2 为朋友整理了「动态规划」题单，他们是：

一定要花时间做掉哦，当然也不用全部做完，以能解决面试中的动态规划问题为准。

作者：liweiwei1419 链接：https://suanfa8.com/dynamic-programming/important-problem 来源：算法吧著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。