1. 导入

2. DP可解

确认一个问题是否DP可解是使用DP算法前最重要的一步。

2.1 相关概念

状态：内存中存储的变量构成了计算机当前的状态。
状态转移：如何由当前状态计算出下一时刻的状态。
空间复杂度：空间复杂度是由状态和状态转移计算所需的变量空间决定的。
时间复杂度：时间复杂度由开始的状态到最终的状态决定的。
阶段：随着问题的解决，在同一个时刻可能会得到的不同状态的集合。举个例子，假如把你放在一个围棋棋盘上的某一点，你每一步只能走一格，因为你可以东南西北随便走，所以你当你同样走四步可能会处于很多个不同的位置。从头开始走了几步就是第几个阶段，走了n步可能处于的位置称为一个状态，走了这n步所有可能到达的位置的集合就是这个阶段下所有可能的状态。
后效性：之前的路线会影响下一步的选择，这称为后效性。

2.2 不同阶段引出的不同算法

假如问题有n个阶段，每个阶段都有多个状态，不同阶段的状态数不必相同，一个阶段的一个状态可以得到下个阶段的所有状态中的几个。那我们要计算出最终阶段的状态数自然要经历之前每个阶段的某些状态。
一个问题是该用递推、贪心、搜索还是动态规划，完全是由这个问题本身阶段间状态的转移方式决定的。

2.2.1 递推：每个阶段只有一个状态

2.2.2 贪心：每个阶段的最优状态都是由上一个阶段的最优状态得到的

贪心算法是动态规划的一个特例。

2.2.3 搜索：每个阶段的最优状态是由之前所有阶段的状态的组合得到的

2.2.4 动态规划：每个阶段的最优状态可以从之前某个阶段的某个或某些状态直接得到而不管之前这个状态是如何得到的

每个阶段的最优状态可以从之前某个阶段的某个或某些状态直接得到，这个性质叫最优子结构，能写出状态转移方程的就说明满足最优子结构。
而不管之前这个状态是如何得到的，这个性质叫无后效性。
动态规划是最优化情况下的分治算法，如何拆分问题，定义问题状态和状态之间的关系，使得问题能够以递推（或者说分治）的方式去解决是动态规划的关键。拆分问题靠的就是状态的定义和状态转移方程的定义。
状态：
状态转移方程：

3. DP经典问题

3.1 斐波那契数列

3.2 最大上升子序列

给定一个数列，长度为N，求这个数列的最长上升（递增）子数列（LIS）的长度.
以1 7 2 8 3 4为例：
这个数列的最长递增子数列是 1 2 3 4，长度为4；
次长的长度为3，包括 1 7 8; 1 2 3 等.

3.3 背包问题

背包问题是经典的NP完全问题，背包容量为不太大的整数时可以使用DP算法求解背包问题。

3.4 其他问题

背包问题. (poj1837,poj1276)
型如下表的简单DP(可参考lrj的书 page149):
E[j]=opt{D+w(i,j)} (poj3267,poj1836,poj1260,poj2533)
E[i,j]=opt{D[i-1,j]+xi,D[i,j-1]+yj,D[i-1][j-1]+zij} (最长公共子序列) (poj3176,poj1080,poj1159)
C[i,j]=w[i,j]+opt{C[i,k-1]+C[k,j]}.(最优二分检索树问题)
较为复杂的动态规划(如动态规划解特别的旅行商TSP问题（poj1191,poj1054,poj3280,poj2029,poj2948,poj1925,poj3034）
记录状态的动态规划. (POJ3254,poj2411,poj1185)
树型动态规划(poj2057,poj1947,poj2486,poj3140)
需要用数据结构优化的动态规划.(poj2754,poj3378,poj3017)
四边形不等式理论.较难的状态DP(poj3133)