algorithm DP

动态规划题目是一眼看上去比较难的题目，DP和DFS有很多联系，DFS经常是可以列出每种情况，而DP只求情况的数目。在常见的算法题目中DP一般分为一维的和两维的，一维DP较为简单，直接用一维数组即可，一般可以直接看出DP[i]和DP[i-x]存在的联系，在通常情况下，一维数组不会全部使用，只需要几个数，所以可以O(n)优化到O(1)。二维DP较难，需要自己抽象出DP[i][j]代表的含义，然后需要找到和矩阵其他元素的关系，二维DP常常有字符串出现，j来代表字符串前j位。二维DP可以通过

一维DP

这里举几个一维DP的题目。

1 斐波那契类型，青蛙跳
f(n)=f(n-1)+f(n-2)

2 数组的连续子集中最大的和 || 变形是连续改为递增 dp[i]代表以a[i]结尾的子集最大的和，连续子集问题有dp[i]=max(dp[i-1]+a[i],a[i])，递增子集问题有dp[i]=max(a[i]>a[k]?dp[k]+a[i]|0=<k<i)

3 用1-26表示26个字母，给定一个数字字符串，求能表示的字母种类如12表示AB或L两种
dp[i]代表前i个字符能表示的种类，dp[i]=a[i]==0?0:dp[i-1] + (0<a[i-1,i]<26)?dp[i-2]:0

4 1-n构成BST的种类
1作为根则左树0个节点，右树n-1个节点，2作为根左1右n-2...f(n)=f(0)*f(n-1)+f(1)*f(n-2)...

5 最长增长子数组长度 dp[i]代表以a[i]结尾的最长增长子数组长度，dp[i]=a[i]>a[i-1]?dp[i-1]+1 else a[i]>a[i-2]?dp[i-2]+1 ....

6 最长先增后减子数组长度 上题的变形，dp1[i]代表以a[i]结尾的最长增长子数组长度，dp2[i]代表以a[i]开头的最长递减数组长度。然后dp[i]=dp1[i]+dp2[i]，返回dp中去头去尾的最大值。

二维DP

1 矩阵路径问题，不用抽象dp[i][j]的含义了，比较简单
1.1 mxn矩阵从左上到右下的路径走法 dp[i][j]=dp[i+1][j]+dp[i][j+1]
1.2 杨辉三角矩阵的第i行第j列值是几 dp[i][j]=dp[i-1][j]+dp[i-1][j-1]
1.3 三角矩阵，从顶到底的路径最大和 dp[i][j]=a[i][j]+max(dp[i+1][j],dp[i+1][j+1])

2 IP地址串去掉.后代表的合法IP有多少种
dp[i][j]代表str[:j]分割成i个小0255的数字有多少种分发。
dp[i][j]可以认为有三个部分的和dp[i]=P1+P2+P3：
P1：str[j]是0255，则看str[:j-1]分割成i-1个有多少种分法，否则0
P2：str[j-1,j]是0255，则看str[:j-2]分割成i-1个有几种分法，否则0
P3：str[j-2,j]是0255，则看str[:j-3]分成i-1个有几种分法，否则0

3 硬币凑钱问题给定已排序的面额[x,x,x,..]硬币凑出n元钱方法多少种
dp[i][j]代表用a[:i]这i种面值凑出j元钱的方法。
如果a[i]>j则dp[i][j]=dp[i-1][j]。否则dp[i][j]有两部分组成。dp[i][j-a[i]]+dp[i-1][j]. 有用一张a[i]和用0张a[i]两种情况

4 和3是一类问题的背包问题，容量为n的背包存放[x,x,x,..]大小的物品每样仅有一个，每种物品价值[y,y,y,..]问最多存放的价格。
dp[i][j]代表只有前i个物品时，容量为j的背包存的最大价值。
如果a[i]>j则dp[i][j]=dp[i-1][j]，否则dp[i][j]=max(dp[i-1][j],b[i]+dp[i-1][j-a[i]])

5 扔鸡蛋，m个鸡蛋，n层楼，检测从第几层楼扔下刚好不碎，求扔的最少次数。
dp[i][j]代表i个鸡蛋从j层楼扔下刚好不碎的最少次数。
第一个从第k层扔，碎了则变成dp[i-1][k-1]没碎变成dp[i][j-k]，因为不缺定碎否，所以取两者的最大值。然后k可以取1~j所以dp[i][j]=min(max(dp[i-1][k-1],dp[i][j-k])|0<k<=j)

6 数组能否分成两部分，使得这两部分的和都是总和的一半
先求和s，奇数直接false，偶数则target=s/2.判断是否能加和出s。
dp[i][j]代表数组前j个数能否加和出i。
dp[i][j]可以根据dp[i][j-1]如果是T则其为T。否则看dp[i-a[i]][j-1]。

7 公共字符串长度，公共字符串是指，前后顺序不变的字符串子集
dp[i][j]代表s1[:i]和s2[:j]的最大公共字符串长度。
dp[i][j]= s1[i]==s2[j] ? dp[i-1][j-1]+1 : max(dp[i-1][j],dp[i][j-1])

8 字符串中最长的回文子串长度
dp[i][j]代表s[i,j]是否是回文。
dp[i][j]= s[i]==s[j] && dp[i+1][j-1] ;记录是true时j-i最大值

9 上题的变种，一个字符串最少cut几次，能分割成每段都是回文
dp与上题意义相同。然后建立cut[i]数组代表s[:i]最少切的次数。
cut[i]= dp[0,i]==true? 0;不需要切.否则如下
cut[i] = min( dp[i,i] ? cut[i-1]+1 ,dp[i-1,i]? cut[i-2]+1....)