#动态规划

状态、方程、边界、次序

子数组最大和

dp[i] 以i为结尾，最大和

dp[i]=max(dp[i],dp[i-1]+num[i])

最长递增子序列（LIS）

dp[i] 以i为结尾，最长子序列长度

j<i&&num[j]<num[i]: dp[i]=max(dp[i],dp[j]+1)

最长公共子序列（LCS） 两个字符串，相同部分最长的长度

abcccdefgh + abcdefghijk = abcdefgh

dp[i][j] s1的前i个字符与s2的前j个字符的最长公共子序列长度

如果：s1[i-1]==s2[j-1]:dp[i][j]=dp[i-1][j-1]+1;

否则：dp[i][j]=max(dp[i-1][j],dp[i][j-1]);

编辑距离  

两个字符串s1、s2，将s1变成s2最小操作几次，可以插入、删除、修改一个字符

dp[i][j] s1的前i个字符与s2的前i个字符的编辑距离

如果：s1[i-1]==s2[j-1]:dp[i][j]=dp[i-1][j-1];

否则：dp[i][j]=min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])+1;

                  插入        删除        修改

背包问题

w重量，v价值，c数量

01（只有一个）

dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i])

完全（有无限个）

k*w[i]>=j:dp[i][j]=max(dp[i-1][j],dp[i-1][j-k*w[i]]+k*v[i])

多重（有限个）

k*w[i]>=j&&k<=c[i]:dp[i][j]=max(dp[i-1][j],dp[i-1][j-k*w[i]]+k*v[i])

混合：以上综合，可以当成多重，0代表无限个

分组混合背包

g代表分组

状态：dp[i][j] 有i组重量为j时的最大价值

方程：

for(int i=1;i<=n;i++){//组

   for(int j=0;j<=m;j++){//重

       for(int g=0;g<组内种数;g++){//种

           for(int k=0;k不超数量不超重量;k++){//个数

               dp[i][j]=max(dp[i][j],dp[i-1][j-k*art[i][g].w]+k*art[i][g].v)

           }

       }

   }

}

存在型背包

给定n种物品以及对应的重量，能否刚好装m重

状态：dp[i][j] 有i种物品，是否可以达到j重

方程：

初始化：dp[i][j]=dp[i-1][j]  

      dp[i][j]=dp[i][j]||dp[i-1][j-w[i-1]];

初始化 dp[0][0]=true;

存在型背包求最大重量（实际问的是有n种物品，最多拿多重）

for(int i=m;i>=0;i--){

   if(dp[n][i]){

       cout<<i;

       break;

   }

}

存在型背包求满包方案数量

int ans=0;

for(int i=0;i<=n;i++){

   if(dp[i][m]) ans++;

}

cout<<ans;

物品可重复时，存在型背包方案数量

dp[i][j]+=dp[i-1][j-k*w[i-1]]