动态规划整理

48 阅读 0 评论 32 点赞

我是靠谱客的博主贪玩芒果，最近开发中收集的这篇文章主要介绍动态规划整理，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

动态规划的基本思想：用一个表来记录所有已解决的子问题的答案。适用于解最优化问题，且是自底向上的。
1.分解最优结构
得到最优解的前提是子问题也是最优解
2.建立递归关系
3.计算最优值

记忆化搜索：记录下来，如果已经计算过就不再计算
uva674
题意：有1,5,10,25,50五种硬币，给出一个数字，问又几种凑钱的方式能凑出这个数。

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn = 8000;
const int coin[5] = {1,5,10,25,50};
int n;
long long dp[maxn][5];
long long solve(int i, int s) {
int j;
if(dp[s][i] != -1) return dp[s][i];
dp[s][i] = 0;
for(j=i; j<5&&s>=coin[j]; j++) {
dp[s][i] += solve(j,s-coin[j]);
}
return dp[s][i];
}
int main() {
int i;
memset(dp, -1, sizeof(dp));
for(i=0; i<5; i++) dp[0][i]=1;//0的时候实际上是花了一个硬币，所以是1
while(scanf("%d", &n) != EOF) {
printf("%lldn", solve(0,n));
}
return 0;
}

可以看出来记忆化搜索是自顶向下的
这题同样可以递推解决（自底向上）

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
const int maxn = 8000;
int n, coin[5]={1,5,10,25,50};
long long dp[maxn] = {1};
int main() {
int i, j;
for(i=0; i<5; i++)
for(j=0; j<maxn-100; j++) {
dp[j+coin[i]] += dp[j];
}
while(scanf("%d", &n) != EOF) {
printf("%lldn",dp[n]);
}
return 0;
}

段最大和问题
uva507
题目大意：
Jill喜欢骑自行车，但是自从他的城市有了公交系统后，他就比较少骑车了，于是他买了一个折叠自行车，这样他就可以把自行车带到公交车上，当他下车后，他就可以继续骑车。
现在b条道路，每条道路有n个公交站点，两个站点间都有一个喜欢值，现在问你能否求出，哪两个站点间的喜欢值最大，如果有多个最大值，输出其中距离最远的站点。

#include<cstdio>
#include<string>
using namespace std;
int s[20005];
int snum;
int main()
{
int n, i, kase=0;
scanf("%d", &n);
while(n--) {
kase++;
scanf("%d", &snum);
for(i=1; i<=snum-1; i++)
scanf("%d", &s[i]);
int st, l, r, sum, maxs;
st=l=r=1;
sum=maxs=0;
for(i=1; i<snum; i++) {
sum += s[i];
if(sum<0) {
sum=0;
st=i+1;
}
if(sum>maxs || (sum==maxs&&(i-st)>(r-l))) {
maxs=sum;
l=st;
r=i;
}
}
if(maxs <= 0) {
printf("Route %d has no nice partsn", kase);
}
else {
printf("The nicest part of route %d is between stops %d and %dn", kase, l, r+1);
}
}
return 0;
}

二维最大和
UVA116：
给你一个n*m的数字表格，找到一条从左到右的路径，使得上面的数字和最小，可越界。
自底向下：从终点开始枚举起点，保证每个子问题都是最优解

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
using namespace std;
const int maxn = 105;
const int INF = 0x3f3f3f3f;
int map[15][maxn];
int dp[15][maxn];
const int dir[3][2]={{0,1},{1,1},{-1,1}};
int n, m;
int path[15][maxn];
void print(int cur, int y) {
if(y != m-1) {
printf(" %d",path[cur][y]+1);
print(path[cur][y],y+1);
}
}
int Dp(int x, int y) {
int i;
if(y>=m) return dp[x][y]=0;
if(dp[x][y] != INF) return dp[x][y];
int a, b;
a = x+dir[0][0];
b = y+dir[0][1];
if(a == -1) a=n-1;
if(a == n) a=0;
dp[x][y] = Dp(a,b)+map[x][y];
path[x][y] = a;
int temp = INF;
for(i=1; i<3; i++) {
a=x+dir[i][0];
b=y+dir[i][1];
if(a == -1) a=n-1;
if(a == n) a=0;
temp = Dp(a,b)+map[x][y];
if(temp == dp[x][y]) {
path[x][y] = path[x][y]<a?path[x][y]:a;
}
else if(temp < dp[x][y]) {
dp[x][y] = temp;
path[x][y] = a;
}
}
return dp[x][y];
}
int main() {
int i, j;
while(scanf("%d%d", &n, &m) != EOF) {
for(i=0; i<n; i++)
for(j=0; j<m; j++) {
scanf("%d", &map[i][j]);
}
for(i=0; i<=n; i++)
for(j=0; j<=m; j++) {
dp[i][j]=INF;
path[i][j]=n;
}
int ans = INF;
int temp, r;
for(i=n-1; i>=0; i--) {
temp=Dp(i,0);
if(temp <= ans) {
ans = temp;
r=i;
}
}
printf("%d", r+1);
print(r,0);
printf("n%dn", ans);
}
return 0;
}

区间DP，矩阵连乘问题
题目：矩阵连乘，求最小运算次数，输出运算优先级（用括号给出）。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdio>
using namespace std;
const int maxn = 15;
const int INF = 0x7fffffff;
int x[maxn],y[maxn];
int d[maxn][maxn], r[maxn][maxn];
int dp(int a, int b) {
if(d[a][b]!=-1) return d[a][b];
r[a][b]=a;
int t,i;
if(a==b) return d[a][b]=0;
d[a][b] = INF;
for(i=a; i<b; i++) {
t=dp(a,i)+dp(i+1,b)+x[a]*y[i]*y[b];
if(t<d[a][b]) {
d[a][b]=t;
r[a][b]=i;
}
}
return d[a][b];
}
void print(int a,int b){
if(a>b) return;
if(a==b) printf("A%d",a+1);
else{
printf("(");
print(a,r[a][b]);
printf(" x ");
print(r[a][b]+1,b);
printf(")");
}
}
int main() {
int n,cas=0,i;
while(scanf("%d", &n) && n) {
memset(d, -1, sizeof(d));
for(i=0; i<n; i++)
scanf("%d%d", &x[i],&y[i]);
dp(0,n-1);
printf("Case %d: ", ++cas);
print(0,n-1);
puts("");
}
return 0;
}

最长子序列：
UVA10405：求第二串相对于第一串的最长序列长度（模板题）（递推：有起点终点）

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
using namespace std;
const int maxn = 1005;
string s1,s2;
int f[maxn][maxn];
int main() {
int i,j;
while(getline(cin,s1)) {
getline(cin,s2);
memset(f,0,sizeof(f));
for(i=1; i<=s1.size(); i++)
for(j=1; j<=s2.size(); j++) {
if(s1[i-1]==s2[j-1]) {
f[i][j]=f[i][j]>(f[i-1][j-1]+1)?f[i][j]:f[i-1][j-1]+1;
}
else {
f[i][j] = f[i-1][j]>f[i][j-1]?f[i-1][j]:f[i][j-1];
}
}
printf("%dn",f[s1.size()][s2.size()]);
}
}

这题用scanf过不了，逻辑是一样的，就是输入改成scanf,对应的是字符串数组不是string，就是过不了，不知道为什么

UVA531
题意：找出两段话连续最长的单词组
主要学习如何输出，就是把I,J用计算方法记录下来，然后的话所有被跳过的单词都是这个值，也就是说，这个算出来的IJ减一的话是上一个找到的单词的位置

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
using namespace std;
char w1[105][32];
char w2[105][32];
int dp[105][105];
int f[105][105];
int num1, num2;
void print(int s, int flag) {
int a=s/1000;
int b=s%1000;
if(a && b) {
print(f[a-1][b-1], 1);
printf("%s", w1[a-1]);
if(flag) printf(" ");
}
}
int main() {
int i,j;
while(cin>>w1[0]) {
num1=1,num2=0;
if(strcmp(w1[0],"#")) {
while(cin>>w1[num1] && strcmp(w1[num1],"#")) {
num1++;
}
}
else num1=0;
while(cin>>w2[num2] && strcmp(w2[num2],"#")) {
num2++;
}
memset(dp, 0, sizeof(dp));
memset(f, 0, sizeof(f));
for(i=1; i<=num1; i++)
for(j=1; j<=num2; j++) {
if(strcmp(w1[i-1],w2[j-1])==0) {
dp[i][j] = dp[i-1][j-1]+1;
f[i][j] = i*1000+j;
}
else if(dp[i-1][j]<dp[i][j-1]) {
dp[i][j] = dp[i][j-1];
f[i][j] = f[i][j-1];
}
else {
dp[i][j] = dp[i-1][j];
f[i][j] = f[i-1][j];
}
}
if(f[num1][num2]) {
print(f[num1][num2],0);
}
printf("n");
}
return 0;
}

DAG最长路

UVA10131
题意：一群大象，每头大象有两个属性1：体重 2：IQ，现在从这些大象里挑出大象来排队，队伍有两个要求，每一头大象的体重必须比前一头大，IQ必须比前一头小，求此队伍的最长长度，并列出队伍中大象的序号，序号按照输入给的顺序，序号从1开始
这题相对上一题有更多的限制条件，道理是一样的，用的记忆化搜索（没有起点和终点）

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn = 1005;
struct node {
int w;
int v;
}e[maxn];
int f[maxn];
int path[maxn];
int num;
int ans;
int dp(int cur) {
if(f[cur]) return f[cur];
int a;
for(int i=0; i<num; i++)
if(e[i].w > e[cur].w && e[i].v<e[cur].v) {
a = dp(i)+1;
if(f[cur] <= a) {
f[cur] = a;
path[cur] = i;
}
}
return f[cur];
}
int main() {
int a, b;
num = 0;
while(scanf("%d%d", &a, &b)!=EOF) {
e[num].w = a;
e[num].v = b;
num++;
}
for(int i=0; i<num; i++) {
path[i] = i;
}
ans = 0;
int flag;
for(int i=0; i<num; i++) {
if(!f[i])
dp(i);
if(ans < f[i]) {
ans = f[i];
flag = i;
}
}
printf("%dn", ans+1);
int i;
for(i=flag; path[i]!=i; i=path[i]) {
printf("%dn", i+1);
}
printf("%dn", i+1);
return 0;
}

uva437
题目:
有n种长宽高为x,y,z的砖头，每种都有无数个。
砖头可以用不同姿势的方向来盖。
砖头a以某种姿势可以盖在砖头b上，当且仅当a的底部的长宽都要比b的底部长宽要小。
问最高可以建多高？
思路和上一题一样的，满足条件的进行递归，记忆化搜索，就是要懂得转化为普通的问题，也就是暴利思想，把所有情况都存储起来
代码：

#include<cstdio>
#include<cstring>
#include<string>
#include<iostream>
using namespace std;
struct stone{
int x, y, z;
}s[35*3];
int m[35*3][35*3];
int h, ans;
int dp[300];
bool check(int i, int j) {
if((s[i].x < s[j].x && s[i].y < s[j].y) || (s[i].x < s[j].y && s[i].y < s[j].x)) return true;
return false;
}
int dfs(int cur) {
if(dp[cur] != -1) {
//
printf("%dn", dp[cur]);
return dp[cur];
}
dp[cur] = s[cur].z;
for(int i=0; i<h; i++)
if(m[cur][i]) dp[cur] = max(dp[cur], dfs(i)+s[cur].z);
//
printf("%dn", dp[cur]);
return dp[cur];
}
int main() {
int n, i, j, kase=0;
while(scanf("%d", &n) && n) {
int x, y, z;
kase++;
h = 0;
for(i=1; i<=n; i++) {
scanf("%d %d %d",&x, &y, &z);
s[h].x = x, s[h].y = y, s[h].z = z;
h++;
s[h].x = x, s[h].y = z, s[h].z = y;
h++;
s[h].x = y, s[h].y = z, s[h].z = x;
h++;
}
memset(m, 0, sizeof(m));
for(i=0; i<h; i++)
for(j=i+1; j<h; j++) {
if(check(i, j)) {
m[i][j] = 1;
}
if(check(j, i)) {
m[j][i] = 1;
}
}
memset(dp, -1, sizeof(dp));
ans = 0;
for(i=0; i<h; i++)
ans = max(ans, dfs(i));
printf("Case %d: maximum height = %dn", kase, ans);
}
return 0;
}

背包问题：
0-1背包
uva562,把硬币分成两堆，两堆的差值尽量小
思路：
就是把总值/2，然后尽量靠近这个值，每个硬币只能用一次，所以是0-1背包

#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;
const int maxn = 105;
int coin[maxn];
int d[maxn][maxn*500];
int main() {
int t,i,j;
int num;
int ssum;
scanf("%d", &t);
while(t--) {
ssum=0;
memset(d,0,sizeof(d));
memset(coin,0,sizeof(coin));
scanf("%d",&num);
for(i=1;i<=num;i++) {
scanf("%d",&coin[i]);
ssum+=coin[i];
}
int sum = ssum/2;
for(i=1; i<=num; i++) {
for(j=0; j<=sum; j++) {
d[i][j]=d[i-1][j];
if(j>=coin[i]) {
d[i][j]=d[i][j]>(d[i-1][j-coin[i]]+coin[i])?d[i][j]:(d[i-1][j-coin[i]]+coin[i]);
}
}
}
printf("%dn",ssum - d[num][sum] - d[num][sum]);
}
return 0;
}

完全背包
uva357，类似于uva674

#include<cstdio>
#include<string>
#include<cstring>
using namespace std;
long long count[32002];
int table[5] = {1, 5, 10, 25, 50};
long long dp(int n) {
count[0] = 1;
int i, j;
for(i=0; i<5; i++)
for(j=table[i]; j<=n; j++)
count[j] += count[j-table[i]];
return count[n];
}
int main() {
int n;
while(scanf("%d", &n)!=EOF) {
memset(count, 0, sizeof(count));
long long ans = 0;
ans = dp(n);
if(ans > 1)
printf("There are %lld ways to produce %d cents change.n", ans, n);
else if(ans == 1)
printf("There is only 1 way to produce %d cents change.n", n);
}
return 0;
}

uva624(0-1背包)
题目：
给不一组数，以及一个目标值，选出相加后最接近这个值得数，每个数用1次

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
using namespace std;
int n,tn;
const int maxn = 10005;
int t[25];
int dp[maxn];
int path[25][maxn];
int main() {
int i,j;
while(scanf("%d", &n) != EOF) {
scanf("%d", &tn);
for(i=0; i<tn; i++) {
scanf("%d", &t[i]);
}
memset(dp, 0, sizeof(dp));
memset(path, 0, sizeof(path));
int flag;
for(i=0; i<tn; i++)
for(j=n; j>=t[i]; j--) {
if(dp[j]<dp[j-t[i]]+t[i]) {
dp[j] = dp[j-t[i]]+t[i];
path[i][j] = 1;
}
}
for(i=tn, j=n; i>=0; i--) {
if(path[i][j]) {
printf("%d ",t[i]);
j -= t[i];
}
}
printf("sum:%dn", dp[n]);
}
return 0;
}

uva10465
完全背包，两种汉堡，各有耗时，求在浪费时间最少的情况下吃的汉堡最多
由于必须是从头开始连续的，所以dp要清成负数，保证并不会有没吃汉堡的时间里与之前吃了汉堡的时间一样的情况


#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
using namespace std;
int dp[10005];
int main() {
int m, n, t, i, j;
while(scanf("%d%d%d", &n, &m, &t) != EOF) {
memset(dp, -10001, sizeof(dp));
dp[0]=0;
for(i=m; i<=t; i++) {
if(dp[i]<dp[i-m]+1) {
dp[i] = dp[i-m]+1;
}
}
for(i=n; i<=t; i++) {
if(dp[i]<dp[i-n]+1)
dp[i]=dp[i-n]+1;
}
int f = t;
while(dp[f]<0) f--;
if(f==t)
printf("%dn", dp[t]);
else {
printf("%d %dn", dp[f],t-f);
}
}
return 0;
}

题目大意：求将n写成若干个正整数的立方和的方法数
这道题的启发是组合问题可以转化为硬币问题

#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
using namespace std;
int cube[25];
long long dp[10005];
int main() {
int n, i,j;
for(i=1; i<=21; i++) cube[i]=i*i*i;
memset(dp, 0, sizeof(dp));
dp[0]=1;
for(i=1; i<=21; i++)
for(j=cube[i]; j<10000; j++)
dp[j] += dp[j-cube[i]];
while(scanf("%d",&n)!=EOF) printf("%lldn",dp[n]);
return 0;
}

制造回文

题意：给出一个字符串，可以添加删除字符，或替换字符，求把它变成回文的最少操作次数。

递推

#include <cstdio>

#include <cstring>

#define min(a, b) ((a) < (b) ? (a) : (b))

const int MAXN = 1010;
int dp[MAXN][MAXN];
char ch[MAXN];
int t, cas;
int main() {
int i, j, k;
scanf("%d", &t);
for(cas=1; cas<=t; cas++) {
scanf("%s", ch);
int len=strlen(ch);
for(i=0; i<len; i++) dp[i][i]=0;
for(i=len-1; i>=0; i--)
for(j=i+1; j<len; j++)
if(ch[i]==ch[j])
dp[i][j]=dp[i+1][j-1];
else
dp[i][j]=min(dp[i+1][j],min(dp[i+1][j-1],dp[i][j-1]))+1;
printf("Case %d: %dn", cas, dp[0][len - 1]);
}
return 0;
}

uva10453
给一个字符串，要求添加最少个字符，把它变成回文串，并输出。
记忆化搜索

#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;
int vis[1005][1005];
char str[1005];
const int inf = 0x7fffffff;
int dp(int x, int y) {
if(vis[x][y] != inf) return vis[x][y];
if(x>=y) {
vis[x][y]=0;
return vis[x][y];
}
if(str[x]==str[y]) vis[x][y] = dp(x+1, y-1);
else vis[x][y] = min(dp(x+1, y), dp(x,y-1))+1;
return vis[x][y];
}
void output(int l, int r) {
if(l>r) return;
if(l==r) {
putchar(str[l]);
return;
}
if(str[l]==str[r]){
putchar(str[l]);
output(l+1,r-1);
putchar(str[r]);
}
else if(vis[l][r] == vis[l+1][r]+1) {
putchar(str[l]);
output(l+1,r);
putchar(str[l]);
}
else {
putchar(str[r]);
output(l,r-1);
putchar(str[r]);
}
}
int main() {
int n, i, j;
while(scanf("%s", str+1) != EOF) {
int len = strlen(str+1);
for(i=1; i<=len; i++)
for(j=1; j<=len; j++)
vis[i][j]=inf;
int a = dp(1,len);
printf("%d", a);
output(1,len);
printf("n");
}
}