算法之动态规划问题
Published by Shangyu Liu,
动态规划亦或者普通的递归，都是子问题的拼装过程，官方的说法是定义状态&定义状态转移方程。
问题举例
经典问题：求数组的最大上升子序列（不要求连续）。
描述网易题目：一排人站立，每个人拥有自己的能力值，选取五个人，五个人中相邻的两个人在队列中不能超过8个人的间隔，要求选取的人满足条件的情况下能力值相乘最大。
描述360题目：两组数，交换两个数使得新数组分别求和后的差最小（推广至交换n个数呢）。
描述01背包问题：n个物品，给定体积价值，给定背包体积，体积不超标的情况下的最大价值方案。
描述Google题目：有一个所有元素求和为零的集合，将其划分成子集，使得每个子集元素求和为零，这样的子集划分的越多越好。
描述头条题目：推箱子问题，n*m的棋盘，有墙有人有箱子，从指定起点将箱子以最短路径推到指定终点。
描述lintcode题目：求n个数字排列的字典序的下一个排列
动态规划需要满足两个条件：1、具有最优子结构（每个阶段的最优状态可以从之前的某个阶段的某个或某些状态【而不是所有状态】直接得到），2、无后效性（而不管这个状态是如何得到的）。所谓后效性就是考虑某阶段的状态是如何得到的，比如棋子走棋盘，本身是无后效性的，但如果加以限制，棋子不能走重复路线这就是有后效性的。目前遇到的题目中并没有有后效性的例子（？我也不确定，感觉没有）
什么是最优子结构：360此问题为什么不能用动归呢，就是因为不具有最优子结构，第二次交换的最优解需要第一次的所有状态直接得到（第一阶段状态数为n），而要考虑第二次交换的具体情况，一下导致了第二阶段的状态数变成了n^2，第三次交换状态数为n^3，相当于累积了第一阶段、第二阶段的状态。因此动态规划的核心是第i个阶段求解完毕后的结果为常数个（比如最大上升子序列为一个【即以第k个数字结尾的序列的最长子序列只有一个】）
如何拆分子问题：如何拆分才能使其拥有最优子结构呢？其实说了这么多形而上的东西，归根结底就是找递推关系，只要能找到递推关系，就能够使用动态规划（求反例）。这往往需要经验，只要定义好了状态，递推关系（状态转移方程）往往是容易的，从上升子序列和网易这两个非常好的例子可以摸出一维和二维的规律，用作常用的模版。
模版思路：
1、一维问题，最大上升子序列。当时的思路是遍历数组，定义的函数参数为数组，返回的值为该数组的最大上升子序列，对于第一个元素，或者在或者不在最大子序列中，不在的话，递归去掉第一个元素的新数组，在的话，找到其后第一个比他大的元素并递归以此元素开头的新数组，并与第一个元素合并成最大子序列，比较这两种情况的较大值即为最终答案。然而这是个典型的错误，因为并非找到的比第一个元素大的那个元素会出现在递归返回的数组中！因此需要改变对状态的定义！这是动态规划最重要的部分，如何描述状态才能得到最优子结构。之前的描述如果是正确的话可以在一步将问题解决，但是失败了，子问题不是最优子结构，无法拼装，考虑到错误的原因，将状态描述为以第i个元素开头的最大上升子序列，最终答案必定是一个以某元素开头的序列，因此取所有状态的最大值即可，这样描述的子问题的状态转移方程就容易了，假设以i开头的最大上生子序列为F(i)，F(i) = max{ F(j)+1, j>i, a[j]>a[i] }。显然，i从大往小填充即可，i的时间复杂度为（n-i），最终时间复杂度为n^2。再次区别360的题目，虽然第i个阶段的状态由后（n-i）个阶段得到，但得到的是一个值，360的题目在每一个阶段得到了n个值。
2、二维问题，网易题目，选择五个人，相邻间距满足条件的情况下，能力值相乘最大。这是与最大上升子序列非常类似的题目，很容易想到这样的定义：F(i)为以i开头的满足间距条件的乘积最大值，这个时候去找状态转移方程的时候发现了问题，F(i)如何利用后面的值呢，很容易想到，F(i)是以i开头的满足条件的最大五人乘积，去掉i之后还有四个人，需要求出i相邻条件的d个以他们开头元素的满足条件的最大四人乘积，于是第二个变量出现了，就是几人，自然问题成为了二维的问题，F(i,j)是以i开头的，满足条件的j个人的最大乘积，则F(i,j) = a[i]*max{F(i+1,j-1),F(i+2,j-1),…F(i+d,j-1)}(d为约束条件)。同样从边界填充这个二维数组即可。更难的例子是01背包问题，第二个维度背包容积若隐若现，非常不明显。
3、其他几个题目似乎只有Google的题目有所难度了，因为这个题目分了好几步，最后一步给出来才会朝动态规划的方向去想，而之前的几步很难朝正确的目标坚定地走而不在中途产生怀疑。元素和为零的集合求最多的和为零的集合的划分，首先列举几个错误的算法思路，先将两个和为零的全部划分成子集，然后三个的，四个的，五个的以此类推。三个和为零的元素合并为一个子集，其他剩余元素为一个子集，只有两个子集，而这三个元素若能拆开使用，可能能划分出三个子集。沿着这个思路往下想，这个集合中总是存在某些元素相加为零的（最差是全部元素相加为零），可以元素本身为零，两个加起来为零，三个加起来为零，对于m个加起来为零的集合，可以拆分成不同的和为零的集合，如果我们定义F(m)为m个和为零的元素最多的0和集合的划分情况，则F(m)
1、回文
2、等差数列
3、预测赢家
4、