Info

数据结构精品课 和 递归算法专题课 限时附赠网站会员，全新纸质书《labuladong 的算法笔记》 出版，签名版限时半价！

读完本文，你不仅学会了算法套路，还可以顺便解决如下题目：

LeetCode	力扣	难度
115. Distinct Subsequences	115. 不同的子序列	🔴
-	剑指 Offer II 097. 子序列的数目	🔴

挺久没写动态规划相关的题目了，本文我带大家复习一下动态规划相关问题的一系列解题套路，然后着重讨论一下动态规划穷举时不同视角的问题。

动态规划解题组合拳

首先，前文 我的刷题心得 讲了，我们刷的算法问题的本质是「穷举」，动态规划问题也不例外，你必须想办法穷举所有可能的解，然后从中筛选出符合题目要求的解。

另外，动态规划问题穷举的过程中会出现重叠子问题导致的冗余计算，所以前文 动态规划核心套路框架 中告诉你如何一步一步把暴力穷举解法优化成效率更高的动态规划解法。

然而，想要写出暴力解需要依据状态转移方程，状态转移方程是动态规划的解题核心，可不是那么容易想出来的。不过，前文 动态规划设计：数学归纳法 告诉你，思考状态转移方程的一个基本方法是数学归纳法，即明确 dp 函数或数组的定义，然后使用这个定义，从已知的「状态」中推导出未知的「状态」。

还没完，比如 高楼扔鸡蛋问题 中对 dp 函数/数组的定义不见得是唯一的，不同的定义会导致状态转移方程发生变化，解题效率也有高低之分，所以我们应该给 dp 函数尽可能想出更合适的定义来解题。

接下来就是本文要着重探讨的问题了：就算 dp 函数/数组的定义相同，如果你使用不同的「视角」进行穷举，效率也不见得是相同的。

关于穷举「视角」的问题，后文 回溯算法穷举视角：子集划分问题 讲了回溯算法中不同的穷举视角导致的不同解法，其实这种视角的切换在动态规划类型问题中依然存在。前文对排列的举例非常有助于你理解穷举视角的问题，这里再简单提一下。

本文剩余内容为会员内容，请先购买 网站会员 ，然后 借助 Chrome 插件解锁网页 或者 点这里 跳转小鹅通查看。