背景

由于没有系统训练方法，很多小朋友在动态规划题目存在着很多的误区，主要表现在这两个方面：

• 不管是什么题，只要有递推方程，一律都叫动态规划
• 不知道什么是动态规划，一道题拿起来不知道怎么思考

第一点，我在上一遍动态规划文章已经说明了动态规划的含义。第二点，我一直在思考如何把动态规划的方法提取出来作为思考的方向。这篇文章主要是与大家讨论动态规划的方法论。

动态规划经典模型

01背包

题目回顾：有n个物品，每个物品的重量是w[i]，价值是c[i]，每个物品只能选择一次，背包所能承受的最大重量是W，求物品能放下背包的最大价值和是多少

这个题可以用数学公式来表达：
规划内容：

$max \{\sum_{1}^{n}a_{i}*c_{i}\}$

约束条件：

$\sum_{1}^{n}a_{i}*w_{i}<=W$

$a_{i} \in \{0,1\}$

拿到一个题目，我们首先要把我们学过的算法拿出来对比，看看是不是相应的模型。比如背包问题，假设第一次碰到这个题，如果用动态规划来思考，我们应该怎么思考呢？

动态规划的模型就是要在现有的变量中找到三种维度：

• 增量计算的顺序
• 中间状态
• 规划目标

动态规划要求增量计算，背包问题无须质疑，只有物品有增量计算的可能，而物品天然保持独立选择，所以物品是在增量计算中遍历的过程。

其次，中间状态是什么？背包问题的中间状态只有两种选择，重量和价值，如果选择重量，我们将0-W定为中间状态，把价值定为规划方向。如果选择价值，我们将0-C定位中间状态，把重量定为规划方向。

怎么选择就看题目的约束条件了。由于W是给定的，数据范围也合适，于是我们选择重量来做中间状态。为啥不选择价值呢？如果题目说的是，价值最大是C，而重量无限，那么我们需要将价值作为规划的中间状态，而重量作为规划方向。

1
2
3

01背包问题：
1、给定n（n<=1000）个物品，每个物品有个重量和价值（w[i], c[i]），在背包总容量为W（W<=1000）的情况下，求问能装下背包的最大价值是多少？
2、给定n（n<=1000）个物品，每个物品有个重量和价值（w[i], c[i]），物品价值C[i] <= 10，在背包总容量为W（W<=10000000）的情况下，求问能装下背包的最大价值是多少？

最长上升子序列

题目回顾：给定一个数组B，求这个数组的最长子序列

这个问题用数学公式来表达：

规划内容：

$max \{sum(a)\}$

约束条件：

$B_{i} < B _{j} (a[i]=1 \bigcap a[j]=1\bigcap i<j)$

$a_{i} \in \{0,1\}$

这个题大家很熟悉了，经典题目来着，解决方案是

$dp[i]=max\{dp[j]+1,B[j]<B[i]]\}$

我们从上面说的思维方式来看这个问题：

• 增量计算的顺序：
  不用讨论，只有一种方式，数组的元素是独立的存在，按数组的先后顺序

• 中间状态：
  动态规划是增量计算，计算第i个元素时，只从前一次中间状态，就可以推出后一次中间状态，因此不应该跟原来数组的元素有关
  所以前面那个式子只是为了让大家方便理解而解的，实际上这个问题的中间状态是：

  $state[p]=max\{sum(a),p为a数组中最后一个等于1的元素值\}$

  整理之后，形成状态转移公式：

  $state[B[i]]=max(max\{state[p],p<B[i]\}, state[B[i]])$

  state是一个最多只有n个元素的映射表

另外，根据式子

$state[B[i]]=max(max\{state[p],p<B[i]\}, state[B[i]])$

还有一个通过单调队列或者线段树解决state变量计算的o(nlogn)算法，这个是另一个题了，大家可以思考一下如何转换一下形成另一个题

总结

动态规划是一种解题思想，也是一种优化方式，可以利用增量迭代来降低复杂度。
例题少，这里暂时给出一个小结论，等待反例验证：

所有独立n个元素的题都可以用动态规划解决

解题步骤：

• 动态规划三大要素：计算顺序，中间状态，规划目标；在题目中分别是什么
• 判断是否能解，需要根据题目的数据范围形成的状态空间，是否超过空间复杂度要求，状态转移方程是否超过时间复杂度要求
• 不能解，能否通过用特殊数据结构优化状态转移方程来解决