DP专题总结

1.动态规划

一个问题如果具有重复子问题,那么可以用动态规划求解,从而减少大量重复计算。

2.数塔问题

image.png

问:从第一层走到最后一层所有路径上的数字相加后最大和是多少?
令dp[i][j]表示第i层第j个数字当前的最大和,则状态转移方程:

边界:,使用choice[i][j]数组记录每一个节点是由下层哪个节点得到的,从而回溯构造结果
程序代码:

#include<cstdio>
#include<algorithm>

using namespace std;

const int maxn = 100;
int numTower[maxn][maxn];
int dp[maxn][maxn];    
int choice[maxn][maxn] = {0};

int main()
{
    int n;

    scanf("%d",&n); //²ãÊý
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<=i;j++)
        {
            scanf("%d",&numTower[i][j]);
        }
    }


    //±ß½ç£º×îºóÒ»²ãµÄ×îÓÅÖµµÈÓÚµ±Ç°Êý
    for(int i=0;i<n;i++)
        dp[n-1][i] = numTower[n-1][i];

    //ÓÉÏÂÖÁÉÏ£¬×´Ì¬×ªÒÆ·½³Ì£º dp[i][j] = maxn(dp[i+1][j] + dp[i+1][j+1]) + numTower[i][j]
    for(int i=n-2;i>=0;i--)
        for(int j=0;j<=i;j++){
            if(dp[i+1][j] >= dp[i+1][j+1]){
                dp[i][j] = dp[i+1][j] + numTower[i][j];
                choice[i][j] = 1;
            }
            else{
                dp[i][j] = dp[i+1][j+1] + numTower[i][j];
                choice[i][j] = 2;
            }
        }
    printf("%d\n",dp[0][0]);
    int j = 0;
    for (int i = 0; i < n; ++i)
    {
        printf("%d",numTower[i][j] );
        if (choice[i][j] == 2)
        {
            j++;
        }
        if(i != n-1)
            printf(" ");
    }
}

3.最大连续子序列和

问题:给定K个整数的序列{ N1, N2, ..., NK },其任意连续子序列可表示为{ Ni, Ni+1, ..., Nj },其中 1 <= i <= j <= K。最大连续子序列是所有连续子序列中元素和最大的一个,例如给定序列{ -2, 11, -4, 13, -5, -2 },其最大连续子序列为{ 11, -4, 13 },最大和为20。现在增加一个要求,即还需要输出该子序列的第一个和最后一个元素。
样例输入
5
-3 9 -2 5 -4
3
-2 -3 -1
0
样例输出
12 9 5
0 -2 -1

令dp[i]表示以i结尾的数字当前最大和,状态转移方程:
dp[i] =max(A[i],dp[i-1]+A[i])
边界:dp[0]=A[0]
程序代码:

#include <cstdio>
#include <cstring>
#include <cmath>

using namespace std;

const int maxn = 10010;
int a[maxn];
int dp[maxn];
int choice[maxn];

int main(int argc, char const *argv[])
{
    int k;
    while((scanf("%d",&k)) && k){
        for(int i=0;i<k;i++)
            scanf("%d",&a[i]);
        dp[0] = a[0];
        choice[0] = 1;
        int maxInd = 0;
        for(int i=1;i<k;i++){
            if(a[i] >= dp[i - 1] + a[i]){
                dp[i] = a[i];
                choice[i] = 1;
            }else{
                dp[i] = dp[i-1] + a[i];
                choice[i] = 2;
            }
            if(dp[i] > dp[maxInd])
                maxInd = i;
        }
        if(dp[maxInd] < 0){
            printf("%d %d %d\n",0,a[0],a[k-1] );
        }else{
            int p = maxInd;
            while(choice[p] == 2)
                p--;
            printf("%d %d %d\n",dp[maxInd],a[p],a[maxInd] );
        }
    }
    return 0;
}

4.最长不下降子序列(LIS)

问题:在一个数字序列中,找到一个最长的子序列(可以不连续),使得这个子序列是不下降的,例如现有序列A={1,2,3,-1,-2,7,9},其最长不下降子序列是{1,2,3,7,9},长度为5。
令dp[i]表示以i结尾的序列当前最长不下降子序列的长度,则状态转移分为两种情况:

  1. 如果存在A[i]之前的元素Aj,使得A[j]\le A[i]dp[j] +1>dp[i],则A[i]可跟在A[j]后形成更长的序列
  2. 如果不存在,那么A[i]只能自己形成一条LIS,长度为1

状态转移方程:
dp[i]=max(1,dp[j]+1),j=1,2,\cdots,i-1\&\&A[j]<A[i]
初始状态:dp[i]=1,i\in\{1,2,\cdots,n\}
程序代码:

#include <cstdio>
#include <cstring>
#include <cmath>

using namespace std;

const int maxn = 10010;
int a[maxn];
int dp[maxn];
int choice[maxn];

int main(int argc, char const *argv[])
{
    int k;
    while((scanf("%d",&k)) && k){
        for(int i=0;i<k;i++)
            scanf("%d",&a[i]);
        dp[0] = a[0];
        choice[0] = 1;
        int maxInd = 0;
        for(int i=1;i<k;i++){
            if(a[i] >= dp[i - 1] + a[i]){
                dp[i] = a[i];
                choice[i] = 1;
            }else{
                dp[i] = dp[i-1] + a[i];
                choice[i] = 2;
            }
            if(dp[i] > dp[maxInd])
                maxInd = i;
        }
        if(dp[maxInd] < 0){
            printf("%d %d %d\n",0,a[0],a[k-1] );
        }else{
            int p = maxInd;
            while(choice[p] == 2)
                p--;
            printf("%d %d %d\n",dp[maxInd],a[p],a[maxInd] );
        }
    }
    return 0;
}

5.最长公共子序列(LCS)

给定两字符串A、B,如sadstory和adminsorry,其最长公共子序列为adsory。
令dp[i][j]为A串的第i号字符和B串的第j号字符之前的LCS长度,状态转移有以下两种情况:
1.如果A[i]==B[j],则dp[i][j]=dp[i-1][j-1]+1
2.否则,dp[i][j]=max(dp[i-1][j],dp[i][j-1])
状态转移方程:
dp[i][j]= \begin{cases} dp[i-1][j-1]+1,A[i]==B[i] \\ max(dp[i-1][j],dp[i][j-1],A[i]!=A[j]) \end{cases}
边界:dp[i][0]=dp[0][j]=0(0\le i \le n,0\le j \le m)
注:使用回溯法可求得具体的公共子串(待补)
程序代码:

#include<cstdio>
#include<algorithm>
#include<cstring>

using namespace std;

const int maxn = 1000;
char A[maxn],B[maxn];
int dp[maxn][maxn];

int main()
{
    gets(A + 1); gets(B + 1); 
    int lenA = strlen(A + 1);
    int lenB = strlen(B + 1);
    for(int i=0;i<= lenA;i++)
        dp[i][0] = 0;
    for(int i=0;i<= lenB;i++)
        dp[0][i] = 0;
    //dp[i][j] = dp[i-1][j-1] + 1,A[i] = A[j]
    //dp[i][j] = max(dp[i-1][j],dp[i][j-1])
    for(int i=1;i<= lenA;i++)
        for(int j=1;j<= lenB;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]);
    printf("%d\n",dp[lenA][lenB]);
}

6.最长回文子串

问题:给定一字符串S,求其最长回文子串长度
如PATZJUJZTACCBCC,最长回文子串为ATZJUJZTA,长度为9
令dp[i][j]表示区间为[i,j]串是否是回文串,状态转移分为以下两种情况:
1.若S[i]==S[j],那么如果区间[i+1,j-1]内的串仍为回文串的话,那么区间为[i,j]的串即为回文串
2.若S[i]!=S[j],那么区间为[i,j]的串肯定不是回文串
状态转移方程:
dp[i][j]= \begin{cases} dp[i+1][j-1],S[i]==S[j] \\ 0,S[i]!=S[j] \end{cases}
边界:dp[i][i]=1,1\le i\le n,dp[i][i+1]=(S[i]==S[i+1]?1:0)
注意:枚举方法
如果按照i,j从小到大的顺序枚举,无法保证dp[i+1][j-1]被计算过,因为只初始化了长度为1和2的串,因此可以按串长度即区间长度进行枚举。
程序代码:

#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;
int const maxn = 1000;
char A[maxn];
int dp[maxn][maxn];

int main()
{
    gets(A);
    int len = strlen(A);

    for(int i=0;i<len;i++)
    {
        dp[i][i] = 1;
        if(i != len - 1 && A[i] == A[i+1])
            dp[i][i+1] = 1;
            ans = 2;
    }

    int ans = 1;
    for(int L = 3;L<=len;L++)
    {
        for(int i=0;i+L-1<len;i++)
        {
            int j = i+L-1;
            if(A[i] != A[j])
                dp[i][j] = 0;
            else
            {
                if(dp[i+1][j-1] == 1)
                {
                    dp[i][j] = 1;
                    ans = L;
                }
                else dp[i][j] = 0;
            }
        }
    }
    printf("%d\n",ans);
}

7.DAG最长路(待)

8.0-1背包问题

问题描述:有n件物品,每件物品的重量为w[i],价值为c[i]。现有一个容量为V的背包,问如何选取物品放入背包,使得背包内物品的总价值最大,其中每种物品只有一件。
令dp[i][v]表示前i种物品恰好能放入重量为v的背包所能得到的总价值,状态转移有以下两种情况:
1.选择第i种物品,那么问题转化为前i-1种物品能够放入重量为v-w[i]的背包所能获得的最大价值。
2.不选择第i种物品,那么当前最大价值即等于前i-1种物品能够放入重量为v的背包所能获得的最大价值。
状态转移方程:
dp[i][v]=max(dp[i-1][v],dp[i-1][v-w[i]]+c[i]),1\le i\le n,w[i]\le v\le V
边界状态:dp[0][v]=0(0\le v \le V)

空间复杂度的优化
注意到dp[i][j]的计算只是依赖于i-1阶段的V个状态,而不依赖于i-1之前的状态,因此可以通过滚动数组策略来去掉物品的维度,状态方程:
dp[v]=max(dp[v],dp[v-w[i]]+c[i])(1 \le i \le n,w[i]\le v \le V)

image.png

当前第i阶段只依赖i-1阶段的值,因此在枚举重量v的时候只能逆序枚举,否则会当前i阶段的值会覆盖i-1阶段的值(后面枚举需要用到)。
程序代码:

#include <cstdio>
#include <algorithm>
#include <cmath>

using namespace std;

const int maxn = 100; //物品最大数
const int maxv = 1000; //背包最大重量
//每件物品的重量,每件物品的价值,重量为v的背包所能装物品的最大价值
int w[maxn], c[maxn], dp[maxv];
int selected[maxn]; //记录每个物品是否被选择 

int main(int argc, char const *argv[])
{
    int n,V;
    scanf("%d%d",&n,&V);
    for(int i=0;i<n;i++)
        scanf("%d",&w[i]);
    for(int i=0;i<n;i++)
        scanf("%d",&c[i]);
    //初始边界,当i=0时,dp[v]=0
    for(int v=0;v<=V;v++)
        dp[v] = 0;
    //注意点:
    //1. 滚动数组来优化空间:每次更新时用到的dp是i-1时刻的dp值,更新后变为i时刻的dp值
    //2. 状态转移方程: dp[v] = max(dp[v],dp[v - w[i]] + c[i])
    //3. 逆序更新:保证i-1时刻的值不被覆盖
    //4. dp[v]此时保存的是重量为v恰好装入物品的最大价值
    //5. 阶段状态思想:本阶段的所有状态可有上一阶段的所有状态推理可得
    //   阶段:可选的不同物品,状态:在给定物品下的不同重量
    //6. 无后效性:第i阶段的所有状态取值仅取决于i-1阶段的状态取值
    //   满足无后效性的问题可用滚动数组来求解,不满足的可以增加维度
    for(int i=1;i<=n;i++){
        for(int v = V;v>=w[i];v--){
            dp[v] = max(dp[v],dp[v - w[i]] + c[i]);
        }
    }
    //寻找最大的dp[v]
    int k = 0;
    for(int v=0;v<=V;v++){
        if(dp[v] > dp[k])
            k = v;
    }
    printf("%d\n", dp[k]);
    return 0;
}

9.完全背包问题

问题描述:有n种物品,每种物品的单件重量为w[i],价值为c[i]。现有一个容量为V的背包,问如何选取物品放入背包,使得背包内物品的总价值最大,其中每种物品都有无穷件。
令dp[i][v]表示前i件物品恰好放入容量为v的背包中所能获得的最大价值,和0-1背包的区别在于:
1.不放第i件物品,那么dp[i][v]=dp[i-1][v],同0-1背包
2.放第i件物品,那么dp[i][v]=dp[i][v-w[i]]+c[i],这里dp[i][v]依赖阶段i的v-w[i]的状态,因为物品数量无限,所以可以重复的放物品i
状态转移方程:
dp[i][v]=max(dp[i-1][v],dp[i][v-w[i]]+c[i]),1\le i \le n,w[i]\le v\le V
边界状态:dp[0][v]=0(0\le v \le V)
同样,可以用滚动数组来去掉物品维度,此时需要正序枚举背包容量,因为阶段i的值依赖当前阶段i,需要使用覆盖的数据,状态转移方程:
dp[v]=max(dp[v],dp[v-w[i]]+c[i])(1\le i \le n,w[i] \le v \le V)

10.完全背包可行方案数的问题

问题描述:传统地,一个货币系统是由1,5,10,20 或 25,50, 和 100的单位面值组成的,现用这些硬币支付面值为A的商品,问有多少种不同的方案,输出字典顺序最小的方案,这些硬币无穷多个。

问题特点:相当于求下列方程解的个数:
a_{1}x_{1}+a_{2}x_{2}+\cdots+a_{n}x_{n}=M
其中a_{1},\cdots,a_{n}表示n个硬币的面值,x_{1},\cdots,x_{n}表示组合方案。
令dp[i][v]表示前i个硬币恰能组成面值为v的方案数,则状态转移方程:
dp[i][v]=dp[i-1][v]+dp[i][v-w[i]]
初始化:dp[0]=1,其余为0
使用滚动数组,状态转移方程可转化为:
dp[v]=dp[v]+dp[v-w[i]]
进行正序枚举面值v即可
程序代码:

#include <cstdio>
#include <algorithm>
#include <vector>

using namespace std;

/*
    1.此类问题为完全背包的可行解个数问题,需要掌握
    2.令dp[i][v]表示前i个物品恰能装满重量为w的方案数
    3.状态转移方程:dp[i][v] = dp[i-1][v] + dp[i][v-w[i]],dp[:][0] = 1
    4.讨论:第一种状态转移:不选物品i,状态转移取决于i-1阶段
    第二种状态转移:选择物品i,由于物品i的个数不受限制,因此
    状态转移取决于第i阶段,可以选择多个物品i,但会受到容量v的限制
    5.可以将上述二维状态转移方程利用滚动数组变成一维
    6.进行正序dp
*/

const int maxn = 30;
const int maxm = 10010;
long long dp[maxm],w[maxn];

int main(int argc, char const *argv[])
{
    int n,V;
    scanf("%d%d",&n,&V);
    for(int i=1;i<=n;i++)
        scanf("%lld",&w[i]);
    //初始化
    dp[0] = 1;
    for(int i=1;i<=V;i++)
        dp[i] = 0;
    for(int i=1;i<=n;i++){
        for(int v=w[i];v<=V;v++)
            dp[v] = dp[v] + dp[v-w[i]];
    }
    printf("%lld\n",dp[V] );
    return 0;
}

11.非完全背包问题

问题描述:有1元、5元、50元、100元、500元的硬币各1、5、10、50、100、500枚。现在要用这些硬币来支付A元,有多少种支付方案。并且输出字典顺序最小的方案。

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 205,033评论 6 478
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 87,725评论 2 381
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 151,473评论 0 338
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 54,846评论 1 277
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 63,848评论 5 368
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 48,691评论 1 282
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 38,053评论 3 399
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 36,700评论 0 258
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 42,856评论 1 300
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,676评论 2 323
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,787评论 1 333
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 33,430评论 4 321
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 39,034评论 3 307
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,990评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,218评论 1 260
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 45,174评论 2 352
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 42,526评论 2 343

推荐阅读更多精彩内容