DP问题各种模型的状态转移方程

53 阅读 0 评论 35 点赞

我是靠谱客的博主羞涩紫菜，最近开发中收集的这篇文章主要介绍DP问题各种模型的状态转移方程，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

转自:http://www.cnblogs.com/10jschen/archive/2012/08/19/2646087.html

1(最长公共子串(注意和最长公共子序列区别)）

两个字符串str1和str2,长度分别为（l1,l2)

dp[i][j]表示以两个字符串分别以第i和第j个字符结尾所能达到的公共子序列的长度，由于下面涉及到i-1和j-1，那么这个时候我们一般从i=1和j=1开始到i<=len1, j<=len2。

if(str[i-1]=str[j-1])

dp[i][j]=dp[i-1][j-1]+1;

if(str[i-1]!=str[j-1])

dp[i][j]=0;

0 ; i = 0或j= 0;

就有 dp = dp[i][j] = dp[i-1][j-1] + 1; i > 0且j> 0 且ch1[i-1]= ch2[j-1];

dp[i][j]= 0; i > 0且j> 0 且ch1[i-1]!= ch2[j-1];

注意dp[i][0]=0(0<=i<=max(l1,l2);dp[0][i]=0(0<=i<=max(l1,l2);

最长公共字串要求在原来字符中满足是连续的，最长公共子序列则不要求

最长公共子序列：

根据最长公共子序列问题的性质，我们可以规定dp[i][j]为字符串1的前i个字符和字符串2的前j个字符的最长公共子序列的长度, 由于下面涉及到i-1和j-1，那么这个时候我们一般从i=1和j=1开始到i<=len1, j<=len2。

1ch1[i-1] = ch2[j-1] ,那么dp[i][j]= dp[i-1][j-1] + 1;

2 ch1[i-1] != ch2[j-1] ,那么我们知道ch1[i]和ch2[j]不可能在同一个公共子序列里出现，那么这个时候的最长的子序列可能以ch1[i]或ch2[j]结尾，那么由于dp[i][j]= max {dp[i-1][j] , dp[i][j-1]};

这个时候所有i=0或j=0的dp[i][j]= 0；

0 ; i = 0或j= 0;

就有 dp = dp[i][j] = dp[i-1][j-1] + 1; i > 0且j> 0 且ch1[i-1]= ch2[j-1];

dp[i][j]= max {dp[i-1][j] , dp[i][j-1]};i > 0且j> 0且ch1[i-1]!= ch2[j-1];

2(最长上升或下降子序列)

给定一个序列a1,a2..........an;

dp[i]表示以ai结尾的最长上升子序列长度(下降相反）

核心代码：

for（i=1；i<=n;i++){

dp[i]=1;

for（k=1;k<i;k++){

if(ak<ai&&dp[i]<dp[k]+1)

dp[i]=dp[k]+1;

}

注意最长不上升或不下降子序列问题

3(最大子序列的和问题)

给定一个序列a1,a2..........an;

求子序列的和最大问题dp[i]表示以ai结尾的子序列和,max为最大子序列和

核心：

1如果输入的数据全部为负数则最大值就是序列中的一个最大值

2如果有正数

for（i=1;i<=n;i++){

dp[i]=dp[i-1]+ai;

if(dp[i]<0)

dp[i]=0;

if(max<dp[i])

max=dp[i];
}

4（数塔问题）

给定一个数组s[n][m]构成一个数塔求从最上面走到最低端经过的路径和最大

我么采用至底向上的思路求解问题（注意从倒数第二行开始）

dp[i][j]表示走到第i行第j个的最大值

那么就有dp[i][j]=max{dp[i-1][j-1],dp[i-1][j]}+s[i][j];

for(i=n-1;i>=1;i--){

for(j=1;j<=i;j++){

dp[i][j]=max{dp[i-1][j-1],dp[i-1][j]}+s[i][j]

}

最后dp[1][1]即为最大值

5（01背包问题）

有N件物品和一个容量为V的背包。第i件物品的体积是v[i]，价值是c[i]。求解将哪些物品装入背包可使价值总和最大。

我们知道对于没一件物品我们有两种可能就是放与不放

dp[i][j]表示第i件物品放入容量为j的背包所得的最大价值

dp[i][j]=max{dp[i-1][j-v[i]]+c[i],dp[i-1][j]};

这里我们从j=V倒推回来的话可以优化成

dp[j]=max{dp[j],dp[j-v[i]]+c[i]};

核心代码：

for（i=1;i<=n;i++）{

for(j=V;j>=0;j--){

if(j>=v[i])

dp[j]=max{dp[j],dp[j-v[i]]+c[i]};

}

dp[v]即为最大的价值

6(完全背包问题）

有N种物品和一个容量为V的背包，每种物品都有无限件可用。第i种物品的体积是v[i]，价值是ｃ[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

这时候对于没见物品就不是放与不放的问题了，而是放0件1件.......

这时候我们可以像01背包一样

dp[i][j]表示容量为ｊ的背包第i件物品是否要再一次放入所以我们要从0-Ｖ顺序循环

dp[i][j]=max{dp[i-1][j-v[i]]+c[i],dp[i-1][j]}(注意这里和01背包一样但是求解的过程不同）

优化后：dp[j]=max{dp[j],dp[j-v[i]]+c[i]};

核心代码：

for（i=1;i<=n;i++）{

for(j=v[i];j<=v;j++){//注意这里是从v[i]开始到Ｖ

if(j>=v[i])

dp[j]=max{dp[j],dp[j-v[i]]+c[i]};

}

注意这列求出的dp[v]是最大的因为一直叠加

7(多重背包问题)

有N种物品和一个容量为V的背包。第i种物品最多有n[i]件可用，每件费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

因为对于第i种物品有n[i]+1种策略：取0件，取1件……取n[i]件。

重点：令dp[i][j]表示前i种物品恰放入一个容量为j的背包的最大价值

状态转移方程：dp[i][j]=max{dp[i-1][v-k*v[i]]+k*c[i]|0<=k<=n[i]};(k表示第i种物品放入ｋ件);

核心代码：

for(i=1;i<=n;i++){

for(j=v;j>=0;j--){

for(k=1;k<=n[i];k++){

if(j>=k*v[i])

dp[i][j]=max(dp[i-1][v-k*v[i]]+k*c[i])
}

}

8: (二维费用的背包问题）

二维费用的背包问题是指：对于每件物品，具有两种不同的费用；选择这件物品必须同时付出这两种代价；对于每种代价都有一个可付出的最大值（背包容量）。问怎样选择物品可以得到最大的价值。设这两种代价分别为代价1和代价2，第i件物品所需的两种代价分别为a[i]和b[i]。两种代价可付出的最大值（两种背包容量）分别为V和U。物品的价值为w[i]；

费用加了一维，只需状态也加一维即可。设f[i][v][u]表示前i件物品付出两种代价分别为v和u时可获得的最大价值。

状态转移方程就是：

f[i][v][u]=max{f[i-1][v][u],f[i-1][v-a[i]][u-b[i]]+w[i]}

9(最大子段和问题(最大子序列的和不同）)

给定一个序列为a1,a2,a3......an;

要求：求出这个序列里面找到一个子段和最大

dp[i]表示以第i个元素结束，求出所有的“以第i个元素结束的连续数组最大和dp[i]

就有：

1如果dp[i-1]>0,无论ai为何值，有dp[i]=dp[i-1]+ai;

2如果dp[i-1]<=0;舍弃，重新令dp[i]=ai;(因为dp[i-1]为负数无论ai为什么值加上去都会减少)

状态转移方程：dp[i]=dp[i-1]+ai (dp[i-1]>0)

dp[i]=ai(dp[i-1]<=0)

12(最大m子段和)

在限制条件增加一维时,可以将状态也相应的增加一维,来进行状态转移

以dp[i][j]表示以第i个元素为结尾,使用j个子段所能达到的最大值(这一维的状态,正是对应了新的限制条件!)这样就很容易写出

状态转移方程:

dp[i][j]= max{ dp[i - 1][j] + a[i], dp[i - k][j - 1] + a[i]}( j - 1 <= k <n - m + j).

1 dp[i - 1][j] + a[i] (把第i个元素包含在最后一个子段内)

2 dp[i - k][j - 1] + a[i], j - 1 <= k < n - m + j(第i个元素单独为一子串)

13矩阵连乘

问题描述：给定一序列的矩阵要求找到一种矩阵连乘的顺序，使得连乘的次数最少

思路：建立递推表达式，利用动态规划的方式(m[i][j]表示第i个矩阵至第j个矩阵这段的最优解,还有对于两个矩阵M(i,j)*S(j,k)则需要i*j*k次乘法)

1显然如果i=j，则m[i][j]这段中就一个矩阵，需要计算的次数为0；

2如果i < j，则m[i][j]=min{m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j]},其中k,在i与j之间游荡，所以i<=k<j;

3因为你要保证在计算m[i][j]查找m[i][k]和m[k+1][j]的时候，m[i][k]和m[k+1][j]已经计算出来了

所以有动态转移方程：

m[i][j]={ 0 , i=j};

m[i][j]={min{m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j]} , i!=j};

m[1][n]即为最终求解

白书上面写道：记忆华搜索固然没有问题，但如果要写成递推，无论按照i还是j的递增或递减均不争确。正确的方法是按照j-i递增的顺序递推，因为长区间的值依赖于短区间的值

模板：

int dp[MAXN][MAXN];//存储最小的就算次数
int s[MAXN][MAXN];//存储断点，用在输出上面

核心代码：

int i , j ,tmp；

for(l= 2 ; l <= n ; l++){//j-i的长度,由于长度为1是相同的矩阵那么为0不用计算
for(i = 1 ; i <= n-l+1 ; i++){//由于j-i =l - 1 , 那么j的最大值为n，所以i上限为 n - l+1;
j = i+l-1;//由于j-i = l - 1 , 那么j = l+i-1
dp[i][j] = dp[i+1][j] + r[i]*c[i]*c[j];//初始化，就是k = i；
s[i][j] = i;
for(k = i+1 ; k < j ; k++){//循环枚举k i < k < j
tmp = dp[i][k] + dp[k+1][j] + r[i]*c[k]*c[j];
if(dp[i][j] > tmp){
dp[i][j] = tmp;//更新为最小值
s[i][j] = k;
}
}
}
}

输出：

//递归调用输出
void output(int i , int j){
if(i == j){
printf("A%d" , i);//当两个相等的时候就不用继续递归就输出A
return;//返回上一层
}

else{
printf("(");
output(i , s[i][j]);
printf(" x ");
output(s[i][j]+1 , j);
printf(")");
}
}

14区间DP

区间动态规划问题一般都是考虑，对于每段区间，他们的最优值都是由几段更小区间的最优值得到，是分治思想的一种应用，将一个区间问题不断划分为更小的区间直至一个元素组成的区间，枚举他们的组合，求合并后的最优值。
1 设F[i,j]（1<=i<=j<=n）表示区间[i,j]内的数字相加的最小代价
2 最小区间F[i,i]=0（一个数字无法合并，∴代价为0）

3 每次用变量k（i<=k<=j-1）将区间分为[i,k]和[k+1,j]两段

         4《区间DP模板，代码》
              for(int p = 1 ; p <= n ; p++){//p是区间的长度，作为阶段
           for(int i = 1 ; i <= n-p ; i++){//i是穷举区间的起点
               int j = i+p;//j为区间的终点
               for(int k = i+1 ; k < j ; k++)//状态转移
                   dp[i][j] = min{dp[i][k]+dp[k+1][j]+w[i][j]};//这个是看具体的状态转移方程

或 dp[i][j] = max{dp[i][k]+dp[k+1][j]+w[i][j]};//求最大

或 dp[i][j] = min{dp[i][k]+dp[k][j]+w[i][j]}//有的是要从k开始不是k+1

}
}