动态规划总结

1.dp[i]表示以A[i]结尾的最值

例子1：最大连续子序列和（洛谷P3009）
dp[i]=max(dp[i-1],dp[i-1]+A[i])

例子2:最长不下降子序列
dp[i]=max(1,dp[j]+1)(j=1,2...i-1&&A[j]<A[i])
（一般不要求连续的都要从一遍历到前一个元素）

---

2.dp[i]表示以i点为起点的xx

例子：DAG的最长路
dp[i]表示从i点出发能得到的最长路径长度
dp[i]=max(dp[j])+length(j->i)(存在j->i)

---

3.dp[i][j]表示从i到j的xx

例子1:最长公共子序列
dp[i][j]表示字符串A的i位与字符串B的j位之间的最长公共子序列
if(A[i]==B[j])
dp[i][j]=dp[i-1][j-1]+1
else
dp[i][j]=max(dp[i-1][j],dp[i][j-1])
边界条件：dp[i][0]=0;dp[0][j]=0;

例子2:最长回文子串
dp[i][j]表示S[i]到S[j]表示的是否为回文子串（注意这里的dp是bool型）
if(S[I]==S[j]&&dp[i+1][j-1]==1)
dp[i][j]=1
else
dp[i][j]=0;
边界：dp[i][i]=1
if(S[i]==S[i+1]) dp[i][i+1]=1;
else dp [I][i+1]=0
实现：枚举子串的长度（从三开始，小于len）
{
枚举子串的起始端点（从0开始，小于len-子串长度+1）
}

---

4.背包问题