动态规划

有关动态规划的算法和练习题整体的归纳与总结

算法理解

  1. 原问题->子问题
  2. 状态
  3. 初始状态
  4. 状态转移方程

    eg.

    hduoj1003 Max Sum

求一串数字的和最大子序列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <iostream>

using namespace std;
struct dp{
    int x,val;
} dp[100000];
//dp[i]保存以i位置结尾的子串的最优解
int main()
{
    int time=0;
    int x=1;
    cin>>time;
    while(time--){
       int num=0;
       int a[100000];
       cin>>num;
       for(int i=0;i<num;i++){
            cin>>a[i];
       }
       dp[0].val=a[0];
       dp[0].x=0;
       for(int i=1;i<num;i++){
            if(dp[i-1].val+a[i]<a[i]){
                dp[i].x=i;
                dp[i].val=a[i];
            }
            else {
                dp[i].x=dp[i-1].x;
                dp[i].val=dp[i-1].val+a[i];
            }
       }
       int max=-1001;
       int start=0,end=0;
       for(int i=0;i<num;i++){
        if(dp[i].val>max){
            max=dp[i].val;
            start=dp[i].x;
            end=i;
        }
       }

       cout<<"Case "<<x++<<":"<<endl;
		cout<<max<<' '<<start+1<<' '<<end+1<<endl;
		if(time)cout<<endl;
    }
    return 0;
}

hduoj2084

经典数塔问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <iostream>
#include <algorithm>
#include <string.h>
#include <stdio.h>

using namespace std;
int dp[1100];
int a[101][101];

int main()
{
    int N;
    scanf("%d",&N);
    while(N--){
        int layer;
        scanf("%d",&layer);
        //输入金字塔
        for(int i=1;i<=layer;i++){
            for(int j=1;j<=i;j++)
                scanf("%d",&a[i][j]);
        }
        for(int i=layer-1;i>=1;i--){
            for(int j=1;j<=i;j++){
                a[i][j]=max(a[i+1][j],a[i+1][j+1])+a[i][j];
            }
        }
        printf("%dn",a[1][1]);
    }

    return 0;
}

hduoj1176

gameboy免费馅饼,求获得的最多馅饼量；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <iostream>
#include <algorithm>
#include <string.h>
#include <stdio.h>

using namespace std;
int dp[110000][20];
//dp表示i时间段在各个位置上的最佳馅饼数
int main()
{
    int n;
    int x,T;
    int maxT=0;
    while(scanf("%d",&n)&&n!=0){
        memset(dp,0,sizeof(dp));
        maxT=0;
        while(n--){
            scanf("%d%d",&x,&T);
            dp[T][x]++;
            if(T>maxT)maxT=T;
        }
        for(int i=maxT-1;i>=0;i--){
            for(int j=0;j<=10;j++){
                if(j==0){
                    dp[i][j]=max(dp[i+1][j],dp[i+1][j+1])+dp[i][j];
                }
                else if(j==10){
                    dp[i][j]=max(dp[i+1][j],dp[i+1][j-1])+dp[i][j];
                }
                else {
                    dp[i][j]=max(max(dp[i+1][j-1],dp[i+1][j]),dp[i+1][j+1])+dp[i][j];
                }
            }
        }
        printf("%dn",dp[0][5]);
    }

    return 0;
}

hduoj1087

Super Jump!跳到比当前大的位置，求从start到end经过的最大和；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <iostream>
#include <algorithm>
#include <string.h>
#include <stdio.h>

using namespace std;
int dp[1100];
int a[1100];
//dp作为以i为最后一步时，得到的最佳分数
int main()
{
    int N;
    while(scanf("%d",&N)!=EOF&&N!=0){
        memset(dp,0,sizeof(dp));
        int i=0;
        int temp=N;
        while(temp--){
            scanf("%d",&a[i]);
            dp[i]=a[i];
            i++;
        }
        for(int j=0;j<N;j++){
            for(int k=0;k<j;k++){
                if(a[j]>a[k]&&dp[k]+a[j]>dp[j]){
                    dp[j]=dp[k]+a[j];
                }
            }
        }
       // for(int kk=0;kk<=N;kk++){printf("%d ",dp[kk]);}
        printf("%dn",*max_element(dp, dp + N));
    }

    return 0;
}

hduoj1159

Common Subsequence经典最长公共子序列问题，构建矩阵；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <iostream>
#include <string.h>
#include <stdio.h>

using namespace std;
int dp[1001][1001];
//dp可能因为太大了，所以需要开在全局
//dp矩阵保存当前2个字符串的最长相同子序列长度
int main()
{
    string a,b;
    while(cin>>a>>b){
        int la=a.length();
        int lb=b.length();
        //cout<<la<<" "<<lb<<endl;
        memset(dp,0,sizeof(dp));
        int m=0;
        for(int i=1;i<=la;i++){
            for(int j=1;j<=lb;j++){
                if(a[i-1]==b[j-1])
                    dp[i][j]=dp[i-1][j-1]+1;
                else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
                if(m<dp[i][j])m=dp[i][j];
            }
        }
        printf("%dn",m);
    }

    return 0;
}