DP-转移方程
- 搞个算法笔记dp的总结，晴神tql了8！！！！
数塔
dp[i][j]为从第i行第j个数字出发的到达最底层的所有路径中能得到的最大和（边界dp[n][j]=f[n][j]）
dp[i][j]=max(dp[i+1][j],dp[i+1][j+1]);
最大子序列和
dp[i]为必须以A[i]结尾的连续序列（边界A[0]）
dp[i]=max(A[i],dp[i-1]+A[i]);
最长不下降子序列（LIS）
dp[i]为以A[i]结尾的最长不下降子序列长度（边界为1）
dp[i]=max(1,dp[j]+1);（j=1,2,…,i-1&&A[j]<A[i]）
最长公共子序列（LCS）
dp[i][j]为字符串A的i号位与字符串B的j号位之前的LCS长度（边界dp[0][j]=0、dp[i][0]=0）
dp[i][j]=dp[i-1][j-1]+1 A[i]==B[j]
max(dp[i-1][j],dp[i][j-1]) A[i]!=B[j]
（可重复）最长公共子序列
dp[i][j]为字符串A的i号位与字符串B的j号位之前的LCS长度（边界dp[0][j]=0、dp[i][0]=0）
dp[i][j]=max(dp[i-1][j],dp[i][j-1])+1 A[i]==B[j]
max(dp[i-1][j],dp[i][j-1]) A[i]!=B[j]
最长回文子串
dp[i][j]为S[i]到S[j]所表示的子串是不是回文子串（边界dp[i][i]=1、dp[i][i+1]=(S[i]==S[i+1])?1:0）
dp[i][j]=dp[i+1][j-1] S[i]==S[j]
0 S[i]!=S[j]
(j=i+L-1)
0-1背包
dp[i][j]为前i件物品恰好装入j容量的背包中能获得的最大价值（边界dp[0][i]、dp[i][0]=0）
dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+c[i]);（i=1 to n，j=w[i] to V）
P.S. 若硬币可能存在w[i]与c[i]合为一体
简化：dp[j]=max(dp[j],dp[j-w[i]]+c[i]);（i=1 to n，j=V to w[i]）
完全背包
dp[i][j]为前i件物品恰好装入j容量的背包中能获得的最大价值（边界dp[0][i]、dp[i][0]=0）
dp[i][j]=max(dp[i-1][j],dp[i][j-w[i]]+c[i]);（i=1 to n，j=w[i] to V）
简化：dp[j]=max(dp[j],dp[j-w[i]]+c[i]);（i=1 to n，j=w[i] to V）
股票系列
1. 任意两天一次买卖的maxProfit
maxProfit=max(maxProfit,prices[i]-prices[mini]);（i=0 to n）
mini随遍历更新
2. 任意两天无限次买卖的maxProfit
maxProfit=max(maxProfit,maxProfit+prices[i]-prices[i-1]);（i=0 to n）
3. 任意两天两次买卖的maxProfit
maxProfit = max(maxProfit,former[i]+latter[i]);
former[i]=max(maxProfit1,prices[i]-prices[mini]); (0 to i的局部最大)
latter[i]=max(maxProfit2,prices[i]-prices[mini]);(i to n的局部最大)
