動(dòng)態(tài)規(guī)劃(三)

一：線性DP

1.數(shù)字三角形

1.1數(shù)字三角形題目

1.2代碼思路

正序思路

倒序思路

1.3代碼實(shí)現(xiàn)(正序and倒序)

正序版本

#include<bits/stdc++.h>
using namespace std;const int N=510,INF=0x3f3f3f3f;
int f[N][N];
int a[N][N];int main(){int n;cin>>n;for(int i=1;i<=n;i++){for(int j=1;j<=i;j++){cin>>a[i][j];}}for(int i=1;i<=n;i++){             for(int j=0;j<=i+1;j++){          //因?yàn)橛胸?fù)數(shù)，所以應(yīng)該將兩邊也設(shè)為-INFf[i][j]=-INF;}}f[1][1]=a[1][1];for(int i=2;i<=n;i++){for(int j=1;j<=i;j++){f[i][j]=a[i][j]+max(f[i-1][j-1],f[i-1][j]);}}int res=-INF;for(int i=1;i<=n;i++) res=max(res,f[n][i]);cout<<res<<endl;
}

倒敘版本(倒序比正序好的地方就在不用考慮邊界問(wèn)題)

#include<bits/stdc++.h>
using namespace std;const int N=510;
int f[N][N];
int n;int main(){cin>>n;for(int i=1;i<=n;i++){for(int j=1;j<=i;j++){cin>>f[i][j];}}for(int i=n;i>=1;i--){for(int j=i;j>=1;j--){f[i][j]=max(f[i+1][j],f[i+1][j+1])+f[i][j];}}cout<<f[1][1]<<endl;
}

2.最長(zhǎng)上升子序列

2.1最長(zhǎng)上升子序列題目

2.2代碼思路

2.3代碼實(shí)現(xiàn)

#include<iostream>
#include<algorithm>
using namespace std;
const int N=1010;
int n;
int a[N],f[N];//a[N]我們用來(lái)保存長(zhǎng)度為n的序列//f[N]表示以指定數(shù)字結(jié)尾的單調(diào)遞增的序列的最大長(zhǎng)度
int main()
{scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&a[i]);}for(int i=1;i<=n;i++){f[i]=1;//只有a[i]一個(gè)數(shù)符合單調(diào)遞增for(int j=1;j<i;j++){if(a[j]<a[i]){f[i]=max(f[i],f[j]+1);}}}int res=0;for(int i=1;i<=n;i++){res=max(res,f[i]);}printf("%d\n",res);return 0;
}

3.最長(zhǎng)公共子序列

3.1最長(zhǎng)公共子序列題目

3.2代碼思路

我覺(jué)得這題的狀態(tài)分成兩半考慮比較方便，按兩個(gè)序列末尾的字符是不是相等來(lái)區(qū)分。

3.3代碼實(shí)現(xiàn)

#include<iostream>
#include<algorithm>
using namespace std;const int N=1010;int n,m;char a[N],b[N];int f[N][N];int main(){scanf("%d%d",&n,&m);scanf("%s%s",a+1,b+1);for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){f[i][j]=max(f[i-1][j],f[i][j-1]);if(a[i]==b[j]) f[i][j]=max(f[i][j],f[i-1][j-1]+1);}}printf("%d\n",f[n][m]);return 0;}

4.石子合并

4.1題目如下

題目分析
假設(shè)有4堆石子:1 3 5 2
i=1,k=2,j=4
f[1,2]:將第一堆和第二堆這兩堆石子合并成一堆石子
f[3,4]:將第三堆和第四堆這兩堆石子合并成一堆石子
所以經(jīng)過(guò)f[1,2]+f[3,4]后我們就成功將1 3 5 2這四堆石子合并成了4 7 這兩堆石子
不過(guò)別忘了題目要求的是將這四堆石子合并成一堆石子
所以我們還需將4 7 這兩堆石子合并成一堆石子
因此還需付出4+7=11的代價(jià)；而11=[1,4]的前綴和
總代價(jià):(1+3)+(5+2)+4+7=22
假設(shè)有4堆石子:1 3 5 2
i=1,k=2,j=4
f[1,2]:將第一堆和第二堆這兩堆石子合并成一堆石子
f[3,4]:將第三堆和第四堆這兩堆石子合并成一堆石子
所以經(jīng)過(guò)f[1,2]+f[3,4]后我們就成功將1 3 5 2這四堆石子合并成了4 7 這兩堆石子
不過(guò)別忘了題目要求的是將這四堆石子合并成一堆石子
所以我們還需將4 7 這兩堆石子合并成一堆石子
因此還需付出4+7=11的代價(jià)；而11=[1,4]的前綴和
總代價(jià):(1+3)+(5+2)+4+7=22

4.2代碼思路

4.3代碼實(shí)現(xiàn)

#include<iostream>
#include<algorithm>
using namespace std;
const int N=310;
int n;
int s[N];
int f[N][N];int main()
{scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%d",&s[i]);for(int i=1;i<=n;i++) s[i]+=s[i-1];for(int len=2;len<=n;len++){for(int i=1;i+len-1<=n;i++){int l=i,r=i+len-1;f[i][r]=1e8;for(int k=l;k<r;k++){f[l][r]=min(f[l][r],f[l][k]+f[k+1][r]+s[r]-s[l-1]);}}}printf("%d\n",f[1][n]);return 0;
}

總結(jié)

??本篇博客涉及了線性dp和區(qū)間dp，還有對(duì)應(yīng)的算法題目講解幫助理解算法，希望對(duì)大家有幫助~