从动态规划的视角重新理解问题
最近在复习算法课的知识，有一节内容专门就是讲基于归纳的算法。所谓归纳，其实是数学上的表述，我们也可以成为动态规划，它们的本质，都可以通过状态转移方程来表示。而这篇文章，就是想深入规范地分析一下在常见的问题中，我们究竟如何来列出状态转移方程。
何为状态转移方程？
顾名思义，状态转移方程其实就是描述不同"状态“之间关系的方程。我们看待问题时，不再是之前的线性思维，而是将所有出现的可能看作一个个互相关联的状态。很多时候我们需要的解（比如全局最优，序列最长等等），就藏在某个状态之中。
状态，是对问题在某一时刻的完整描述。
它必须要满足无后效性。也就是说，未来的决策不会受到到达该状态历史的影响。通俗点说，在做未来的决策时，我们不需要考虑状态是如何形成的，我们只要知道这个状态的情况。
这里的描述有点类似于数学中的数学归纳法：假设对于前 n-1 个规模的数据结论成立，在此基础上证明对规模为 n 的数据也成立。
一般形式的状态转移方程如下：
$$ dp(state) = opt\left\{dp(pre_state) + cost\right\} $$dp是定义在状态上的值函数，可以代表最优值，可达性…opt是聚合操作：$max、min、 \sum 、OR$等prev_state是状态转移来源，必须满足拓扑序cost就是从前驱状态转移到当前状态的成本
在这里的命名似乎会让人有一种从后往前递归的错觉，在大部分情况下可以这么理解，但其实只要能够满足拓扑序即可（这里相当于吧每个状态理解为了一个节点，形成了一张图）
此外还有一个比较重要的参数：
- 边界条件：用于递归方程的终止，一般也作为算法的起点或终点
How to write a DP equation
我们可以以背包问题来描述写状态转移方程的流程。
- 定义状态
这是一个显然的回答，不过很多人容易和下面的定义值函数语义混在一起。具体来说，状态就是对这个问题的缩小版的信息聚合。我们可以问自己：“在不回看历史的情况下，我需要知道那些信息，才能做出最优决策？
在背包问题中，我们需要知道的就是能够取哪些物品，以及背包剩余容量。
其实也可以这样理解状态的定义，它就是对原问题的一个复述，只不过有些信息需要改变，而这个需要改变的信息，其实就是我们的状态。
- 定义值函数
dp
我们必须用十分精确的自然语言回答清楚，dp(state)代表什么？。这是最关键的工作，往往也觉得能否成功写出正确的状态转移方程。例如：
dp[i][j]代表只考虑前i件物品，背包容量为j是，能取得的最大值
而不是当第i件物品必须放进容量为j的背包时，能取到的最大值。这或许也是一个状态，但是写出状态转移方程却很困难
- 枚举“最后一步决策”
枚举最后一步的可能，每一种可能其实就对应着一个子问题，从而对应着一个状态。
比如在背包问题中，所谓的最后一步决策只有两种，第i件物品放入背包 和 第i件物品不放入背包。于是这就得到了我们所需要的两中 prev_state。
- 确定边界和拓扑序
确保计算 dp(state)时，所有的 dp(prev_state)都可以视为已经计算好的，尤其是边界情况，需要手动标注一下。例如 dp[0][j]=dp[i][0]=0.
这样，我们可以得到0-1背包问题的状态转移方程如下：
$$ dp[i][j] = \max \left\{ dp[i-1][j] , dp[i-1][j-weight[i]] + value[i]\right\} $$不同问题结构下DP方程形式
状态和值函数的定义是十分灵活的，上面的背包问题只是其中一种形式，下面是按照不同的问题结构来分类的一些例题
线性 DP：状态沿序列推进
最长递增子序列：
dp[i]代表以第i个数结尾的最擦行递增子序列长度
最长公共子序列
dp[i][j]代表字符串s前i个字符和字符串t前j个字符的最擦行公共子序列长度。
背包 DP：资源约束下的选择
刚才的0-1背包问题已经作为例子了，下面考虑完全背包问题（每个物品可以选无数次）
dp[i][j]依然表示只考虑前i个物品，背包容量为j时的最大价值
可以发现，它和0-1背包问题的主要区别就是，原来的dp[i][j-weight[i]]变成了f[i][j − weight[i]]，这意味着第i个物品可以继续选。
区间DP：问题定义在区间上
状态形如 dp[i][j]，表示区间[i , j]上的最优解。这个时候一般最后一步决策不在i或者j,而是区间中的某个位置 k.
我们以矩阵链乘问题为例：
dp[i][j]表示将第 i 个矩阵到第j个矩阵相差的最小运算次数。
解决这类问题是将区间划分成两端，在计算分割点处的代码。所以需要枚举位置k.
$$ dp[i][j]=\max_{i\le k <j} \left\{ dp[i][k] + dp[k+1][j] + p_{i} \cdot p_{k+1} \cdot p_{j+1} \right\} $$矩阵链乘问题
给定一个矩阵链 $A_1,A_2,A_3 ... A_n$ ，找到完全括号化（即确定乘法顺序）的方式，使得标量乘法的总次数最少。
树形 DP：状态定义在树节点上
以节点u 为根的⼦树作为⼦问题，利⽤树的递归结构。这里以树的最大独立集为例：
dp[u][0/1]表示以u为根的子树中，u不选（或选）时，子树的最大权重。如果选了u,则子节点不能选取，否则子节点自由选取。
树的最大独立集问题
在一棵树中，找到一个顶点子集，使得子集中任意两个顶点都不相邻（即没有边直接连接它们），并且该子集的大小最大
计数 DP：值函数是⽅案数
把 max/min 切换为 $\sum$ ，问题就从最优化变成计数了。
比如常见的斐波那契数列:
$$ f[i]=f[i-1]+f[i-2] $$还有整数划分问题（将 n 拆分为正整数之和的⽅案数）:
dp[i][j]表示⽤不超过i 的正整数组成 j 的⽅案数
dp[i-1][j]表示没用到i,dp[i][j-1]表示用到了i. 其实可以理解为完全背包问题的变体。
总之，介绍了这么多种动态规划的方法，想必读者们对于状态转移方程的写法十分熟悉了。
从状态的角度来分析问题，可以为问题提供一种新的视角。有些问题如果正面入手其实是很难直接想出一个算法的，但是动态规划让我们能够将所有的复杂度一层层解耦，我们可以专注于状态间的转移，而所有的状态可以通过递归去求解出来。