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的局部最大)

4. 任意两天无数次买卖的maxProfit（手续费k）