精华内容
下载资源
问答
  • 最长递增公共子序列、最长公共子串、最小编辑代价等经典动态规划问题的详细代码
  • 面试经典动态规划问题

    千次阅读 2017-02-21 20:25:51
    经典动态规划问题三角数塔问题设有一个三角形的数塔,顶点为根结点,每个结点有一个整数值。从顶点出发,可以向左走或向右走,如图所示:要求从根结点开始,请找出一条路径,使路径之和最大,只要输出路径的和。思路...

    经典动态规划问题

    三角数塔问题

    设有一个三角形的数塔,顶点为根结点,每个结点有一个整数值。从顶点出发,可以向左走或向右走,如图所示:

    图1

    要求从根结点开始,请找出一条路径,使路径之和最大,只要输出路径的和。

    思路

    从叶节点倒推回根,因为每个节点只可能向左或者向右,所以转移方程为

    dp[i][j] = num[i][j] + max(dp[i+1][j],dp[i+1][j+1])

    代码

    #include <stdio.h>
    #include <stdlib.h>
    
    #define MAXN 101
    
    int n,d[MAXN][MAXN];
    int a[MAXN][MAXN];
    
    void fnRecursive(int,int);
    //递推方法函数声明
    int fnMemorySearch(int,int);
    //记忆化搜索函数声明
    
    int main()
    {
        int i,j;
        printf("输入三角形的行数n(n=1-100):\n");
        scanf("%d",&n);
        printf("按行输入数字三角形上的数(1-100):\n");
        for(i=1; i<=n; i++)
            for(j=1; j<=i; j++)
                scanf("%d",&a[i][j]);
        for(i=1; i<=n; i++)
            for(j=1; j<=i; j++)
                d[i][j]=-1;//初始化指标数组
        printf("递推方法:1\n记忆化搜索方法:2\n");
        int select;
        scanf("%d",&select);
        if(select==1)
        {
            fnRecursive(i,j);//调用递推方法
            printf("\n%d\n",d[1][1]);
        }
        if(select==2)
        {
            printf("\n%d\n",fnMemorySearch(1,1));//调用记忆化搜索方法
        }
        else
            printf("输入错误!");
    
            return 0;
    }
    
    void fnRecursive(int i,int j)
    //递推方法实现过程
    {
        for(j=1; j<=n; j++)
            d[n][j]=a[n][j];
        for(i=n-1; i>=1; i--)
            for(j=1; j<=i; j++)
                d[i][j]=a[i][j]+(d[i+1][j]>d[i+1][j+1]?d[i+1][j]:d[i+1][j+1]);
    }
    
    int fnMemorySearch(int i,int j)
    //记忆化搜索实现过程
    {
        if(d[i][j]>=0) return d[i][j];
        if(i==n) return(d[i][j]=a[i][j]);
        if(fnMemorySearch(i+1,j)>fnMemorySearch(i+1,j+1))
            return(d[i][j]=(a[i][j]+fnMemorySearch(i+1,j)));
        else
            return(d[i][j]=(a[i][j]+fnMemorySearch(i+1,j+1)));
    }

    硬币问题

    有n种硬币,面值分别为V1,V2,…,Vn, 每种有无限多。给定非负整数S,可以选用多少硬币,使得面值之和恰好为S,输出硬币数目的最小值和最大值。(1<=n<=100,0<=S<=10000,1<=Vi<=S)。

    思路

    完全背包,可以选择无限次某个物品,来达到某个(重量)。

    把S看做重量和,把硬币的面值看重量,把硬币个数当做是价值(也就是1)。

    代码

    #include <stdio.h>
    #include <stdlib.h>
    
    #define INF 100000000
    #define MAXNUM 10000
    #define MONEYKIND 100
    
    int n,S;
    int V[MONEYKIND];
    int min[MAXNUM],max[MAXNUM];
    
    void dp(int*,int*);
    //递推方法函数声明
    void print_ans(int*,int);
    //输出函数声明
    
    int main()
    {
        int i;
        printf("输入硬币的种数n(1-100):\n");
        scanf("%d",&n);
        printf("输入要组合的钱数S(0-10000):\n");
        scanf("%d",&S);
        printf("输入硬币种类:\n");
        for(i=1; i<=n; i++)
        {
            scanf("%d",&V[i]);
        }
        dp(min,max);
        printf("最小组合方案:\n");
        print_ans(min,S);
        printf("\n");
        printf("最大组合方案:\n");
        print_ans(max,S);
        return 0;
    }
    
    void dp(int *min,int *max)
    //递推过程实现
    {
        int i,j;
        min[0] = max[0] = 0;
        for(i=1; i<=S; i++)//初始化数组
        {
            min[i]=INF;
            max[i]=-INF;
        }
        for(j=1; j<=n; j++)
            for(i=1; i<=S; i++)
                if(i>=V[j])
                {
                    if(min[i-V[j]]+1<min[i])
                    {
                        min[i]=min[i-V[j]]+1;//最小组合过程
                        //printf("%d\n",min[i]);
                    }
                    if(max[i-V[j]]+1>max[i])
                        max[i]=max[i-V[j]]+1;//最大组合过程
                }
    }
    
    void print_ans(int *d,int S)
    //输出函数实现
    {
        int i;
        for(i=1; i<=n; i++)
            if(S>=V[i]&&d[S]==d[S-V[i]]+1)
            {
                printf("%d-",V[i]);
                print_ans(d,S-V[i]);
                break;
            }
    }

    矩形嵌套问题

    有n个矩形,每个矩形可以用两个整数a,b描述,表示它的长和宽。矩形X(a,b)可以嵌套在矩形Y(c,d)中,当且仅当a

    思路

    预处理一个二维矩阵,G[i][j]表示第i个矩阵可以被套进第j个矩阵里。

    然后用记忆化搜索爆搜,时间复杂度O( N2 )

    代码

    #include <stdio.h>
    #include <stdlib.h>
    #define MAXNUM 100//矩形的最大个数
    struct Rect
    {
        int x;
        int y;
    };
    
    int n;//矩形个数
    struct Rect rect[MAXNUM];
    int G[MAXNUM][MAXNUM];//邻接有向图
    int d[MAXNUM];//过程数组
    
    int dp(int i,int G[MAXNUM][MAXNUM]);
    
    int main()
    {
        int i,j,z;
        printf("输入矩形个数n(1-100):\n");
        scanf("%d",&n);
        printf("输入矩形的长和宽:\n");
        for(i=1; i<=n; i++)
        {
            scanf("%d",&rect[i].x);
            scanf("%d",&rect[i].y);
        }
        for(i=1; i<=n; i++)
            for(j=1; j<=n; j++)
            {
                if(rect[i].x<rect[j].x&&rect[i].y<rect[j].y || rect[i].y<rect[j].x&&rect[i].x<rect[j].y )
                    G[i][j]=1;
            }
        printf("输入要开始的矩形z:\n");
        scanf("%d",&z);
        //printf("%d-",z);
        int temp = dp(z,G);
        printf("最大可嵌套个数:%d\n",temp);
        return 0;
    }
    
    int dp(int i,int G[MAXNUM][MAXNUM])
    {
        int j;
        if(d[i]>0)
            return d[i];
        d[i]=1;         //嵌套自己本身
        for(j=1; j<=n; j++)
            if(G[i][j])
                if(dp(j,G)+1>d[i])
                {
                    d[i]=dp(j,G)+1;
                }
        return d[i];
    }

    最长不下降序列问题

    设有一个正整数序列b1,b2,b3,……,bn,若下标为i1

    思路

    两种解法,一种是 O(N2) 的解法,比较简单。dp[i]表示以num[i]结尾的最长上升子序列。
    另一种是 Nloh(N) 的解法,思路是,记录现阶段的最长上升子序列d[i],然后对于每一个num[i],若num[i]大于d[len(d)-1],则在d数组后面加上num[i];否则,在d数组中用二分搜索找出第一个大于num[i]的值,并替换为num[i],这样最长上升子序列长度不变,但是得到了一个更有潜力成为最长上升子序列的子序列。

    
    #include<cstdio>
    #include<algorithm>
    using namespace std;
    
    int a[40005];
    int d[40005];
    
    int main()
    {
        int n;
        scanf("%d",&n);
        for (int i=1;i<=n;i++) scanf("%d",&a[i]);
        if (n==0)  //0个元素特判一下 
        {
            printf("0\n");
            return 0;
        }
        d[1]=a[1];  //初始化 
        int len=1;
        for (int i=2;i<=n;i++)
        {
            if (a[i]>=d[len]) d[++len]=a[i];  //如果可以接在len后面就接上 
            else  //否则就找一个最该替换的替换掉 
            {
                int j=upper_bound(d+1,d+len+1,a[i])-d;  //找到第一个大于它的d的下标 
                d[j]=a[i]; 
            }
        }
        /*
        for (int i=2; i<=n; i++)
        {
            len = 0;
            for(int j=1; j<i; j++)
                if((a[i]>=a[j])&&(d[j]>len))
                    len=b[j];
            if(len>0)
                d[i]=len+1;
        }
        */
        printf("%d\n",len);    
        return 0;
    }

    0-1背包问题

    给定n种物品和一背包。物品i的重量是wi,其价值为vi,背包的容量为C。问应如何选择装入背包的物品,使得装入背包中物品的总价值最大?

    代码

    #include <stdio.h>
    #include <stdlib.h>
    
    #define MAXN 100//物品种类最大数量
    
    int w[MAXN],V[MAXN];
    int C;//最大容量
    int n;//物品种类
    int d[MAXN][MAXN];
    int jMax;
    
    int min(int,int);
    //两数之间的最小值
    int max(int,int);
    //两数之间的最大值
    void print_ans(int d[][MAXN],int,int);
    //构造最优解并输出
    
    int main()
    {
        int i,j;
        printf("输入物品种类数n(1-100):\n");
        scanf("%d",&n);
        printf("输入每个种类的重量:\n");
        for(i=1; i<=n; i++)
        {
            scanf("%d",&w[i]);
        }
        printf("输入每个种类的价值:\n");
        for(i=1; i<=n; i++)
        {
            scanf("%d",&V[i]);
        }
        printf("输入背包的容量C:\n");
        scanf("%d",&C);
    
    
        jMax=min(C,w[n]-1);
        for(j=0; j<=jMax; j++)
            d[n][j]=0;
        for(j=w[n]; j<=C; j++)
            d[n][j]=V[n];
    
        for(i=n-1; i>1; i--)
        {
            jMax=min(C,w[i]-1);
            for(j=0; j<=jMax; j++)
                d[i][j]=d[i+1][j];
            for(j=w[i]; j<=C; j++)
                d[i][j]=max(d[i+1][j],d[i+1][j-w[i]]+V[i]);
        }
        d[1][C]=d[2][C];
        if(C>=w[i])
            d[1][C]=max(d[1][C],d[2][C-w[i]]+V[1]);
    
    
    
        printf("最大可容纳:%d\n",d[1][C]);
        return 0;
    }
    
    int min(int x,int y)
    {
        if(x>y)
            return y;
        else
            return x;
    }
    
    int max(int x,int y)
    {
        if(x<y)
            return y;
        else
            return x;
    }

    数字游戏问题

    小W发明了一个游戏,他在黑板上写出了一行数字a1,a2,a3,……,an,然后给你M个回合的机会,每回合你可以从中选择一个数字擦去它,接着剩下来的每个数字ai都要递减一个值bi。如此重复m个回合,所有你擦去的数字之和就是你所得的分数。
    编程算算,对于每个a和b序列,可以得到的最大得分是多少。
    输入样例:
    3 {数字个数n}
    3 {回合数m}
    10 20 30 {n个原始序列}
    4 5 6 {n个每回合每个数字递减的值}
    输出样例:
    47

    思路

    让a[i]和b[i],关于b降序排列。减少得多的先被擦掉,就可以让剩下的和尽可能的大。(但是总觉得好像)

    dp[i][j]表示前i个数字在第j轮的时候的最大取值。

    dp[i][j] = max(dp[i-1][j], dp[i-1][j-1]+a[i]-b[i]*(j-1))

    代码

    #include <stdio.h>
    #include <stdlib.h>
    
    #define MAXNUM 100
    
    int n;//数字个数
    int m;//回合数
    int Num[MAXNUM];//原始数据数组
    int DescNum[MAXNUM];//递减数据数组
    int F[MAXNUM][MAXNUM];//过程数组
    
    void swap(int &,int &);
    //交换两个整数
    int max(int ,int );
    //取两个中的最大值
    
    int main()
    {
        int i,j;
        printf("输入数字的个数n(1-100):\n");
        scanf("%d",&n);
        printf("输入回合数m(1-100)<=n:\n");
        scanf("%d",&m);
        printf("输入n个原始序列:\n");
        for(i=1; i<=n; i++)
        {
            scanf("%d",&Num[i]);
        }
        printf("输入n个递减的数字:\n");
        for(i=1; i<=n; i++)
        {
            scanf("%d",&DescNum[i]);
        }
    
    
        for(i=1; i<=n; i++)
        {
            for(j=i+1; j<=n; j++)
            {
                if(DescNum[i]<DescNum[j])
                {
                    swap(Num[i],Num[j]);
                    swap(DescNum[i],DescNum[j]);
                }
            }
        }
    //    for(int i = 1; i<=n; i++)
    //        printf("%d ", DescNum[i]);
        for(i=1; i<=n; i++)
        {
            F[i-1][0]=0;
            for(j=1; j<=m; j++)
                F[i][j]=max(F[i-1][j],F[i-1][j-1]+Num[i]-DescNum[i]*(j-1));
        }
    
    
        printf("得分:%d\n",F[n][m]+DescNum[1]);
        return 0;
    }
    
    void swap(int &x,int &y)
    {
        int temp;
        temp = x;
        x = y;
        y = temp;
    }
    
    int max(int x,int y)
    {
        if(x<y)
            return y;
        else
            return x;
    }
    

    挖地雷

    在一个地图上有N个地窖(N<=200),每个地窖中埋有一定数量的地雷。同时,给出地窖之间的连接路径,并规定路径都是单向的。某人可以从任一处开始挖地雷,然后沿着指出的连接往下挖(仅能选择一条路径),当无连接时挖地雷工作结束。设计一个挖地雷的方案,使他能挖到最多的地雷。

    思路

    类似第一题

    代码

    #include <stdio.h>
    #include <stdlib.h>
    
    #define MAXNUM 200
    
    int n;//地窖的个数
    int w[MAXNUM];//每个地窖中的地雷数
    int Sum[MAXNUM];//挖到的地雷总数
    int G[MAXNUM][MAXNUM];//形成的图
    int next[MAXNUM];//记录路径
    int max;//最大值
    int start;
    
    //void init(int G[MAXNUM][MAXNUM]);
    //void init2(int n[MAXNUM]);
    
    int main()
    {
        int i,j,x,y;
        printf("输入地窖的个数n(1-200):\n");
        scanf("%d",&n);
        printf("输入各个地窖中的地雷数:\n");
        for(i=1;i<=n;i++)
        {
            scanf("%d",&w[i]);
        }
        //init(G);//初始化有向图
        printf("输入各个地窖之间的链接(x,y):\n");
        scanf("%d,%d",&x,&y);
        while(x!=0&&y!=0)
        {
            G[x][y]=1;
            scanf("%d,%d",&x,&y);
        }
        //init2(Sum);
    
        Sum[n]=w[n];
        for(i=n-1;i>=1;i--)
        {
            for(j=i+1;j<=n;j++)
            {
                if(G[i][j]&&Sum[j]>Sum[i])
                {
                    Sum[i]=Sum[j];
                    next[i]=j;
                }
            }
            Sum[i] += w[i];
        }
        max = 0;
        for(i=1;i<=n;i++)
        {
            if(Sum[i]>max)
            {
                max=Sum[i];
                start = i;
            }
        }
    
    
        printf("最大路径:");
        printf("%d-",start);
        while(next[start]!=0)
        {
            printf("%d-",next[start]);
            start = next[start];
        }
        printf("最大挖雷数:%d\n",max);
        return 0;
    }
    

    最小代价子母树

    设有n堆沙子排成一排,其编号为1,2,3,…,n(n≤100)。每堆沙子有一定的数量,如下表
    13 7 8 16 21 4 18
    现在要将n堆沙子归并成一堆。归并的过程为每次只能将相邻的两堆沙子堆成一堆,这样经过n-1次归并之后最后成为一堆,如上面7堆沙子,可以有多种方法归并成一堆,归并的代价是这样定义的,将两堆沙子归并为一堆时,两堆沙子数量的和称为归并2堆沙子的代价。由此可见,不同归并过程得到的总的归并代价是不一样的。
    问题:n堆沙子的数量给出之后,找出一种合理的归并方法,使总的归并代价为最小。
    [输入格式]
    n {表示沙子的堆数, 2<=n<=100}
    a1 a2 … an {表示每堆沙子的数量,1<=Ai<=100}
    [输出格式]
    x {表示最小的归并总代价 }
    输入样例:
    7
    13 7 8 16 21 4 18
    输出样例:
    239

    思路

    典型的区间dp

    代码

    #include <STDIO.H>
    #include <STDLIB.H>
    
    #define INF 1000000
    #define MAXNUM 100
    
    int n;//沙子的堆数
    int Num[MAXNUM];//每堆沙子的数量
    int F[MAXNUM][MAXNUM];//过程函数
    int G[MAXNUM][MAXNUM];
    
    int fnMin(int ,int );
    //返回两个数的最小值
    
    int main()
    {
        int i,j,k,m,L,t;
        printf("输入沙堆的堆数n(1-100):\n");
        scanf("%d",&n);
        printf("输入每堆中沙子的个数:\n");
        for(i=1; i<=n; i++)
        {
            scanf("%d",&Num[i]);
            G[i][i]=Num[i];
            F[i][i]=0;
        }
        for (m=n-1;m>=1;m--)
        {
            for (i=1;i<=m;i++)
            {
                L=n-m+1;
                j=i+L-1;
                for (k=i;k<=j;k++)
                {
                    G[i][j]=G[i][j]+G[k][k];
                }
                F[i][j]=INF;
                for (k=i;k<=j-1;k++)
                {
                    t=F[i][k]+F[k+1][j]+G[i][j];
                    if (t<F[i][j])
                    {
                        F[i][j]=t;
                    }
                }
            }
        }
        printf("最小代价:%d\n",F[1][n]);
        return 0;
    }

    数字移动问题

    给出一个1到n的排列,每次可以移动一个数到一个任意位置。问要达到状态1,2,3……n至少移动多少次?
    Sample Input
    5
    2 1 4 5 3
    Sample Output
    2

    思路

    计算出最长上升子序列,然后用总长度减去它。

    代码

    #include <stdio.h>
    #include <stdlib.h>
    
    #define MAXNUM 100//最大数字个数
    #define INF 100000000
    
    int n;//数字个数
    int Num[MAXNUM];//未排序数字
    int Last[MAXNUM];
    
    void update(int x,int y,int L[],int N[],int i);
    //递归函数
    
    int main()
    {
        int i,j;
        int lis;
        printf("输入数字的个数n(1-100):\n");
        scanf("%d",&n);
        printf("输入数字:\n");
        for(i=1;i<=n;i++)
        {
            scanf("%d",&Num[i]);
        }
    
        lis = 0;
        Last[lis]=-INF;
        for(i=1;i<=n;i++)
        {
            if(Num[i]>Last[lis])
            {
                lis++;
                Last[lis]=Num[i];
            }
            else
    
            update(0,lis,Last,Num,i);
        }
    
    
        printf("最少移动次数:%d\n",n-lis);
        return 0;
    }
    
    void update(int x,int y,int L[],int N[],int i)
    {
        if(x==y)
        {
            L[x]=N[i];
        }
        else
        {
            if(L[(x+y)/2]>N[i])
            {
                update(x,(x+y)/2,L,N,i);
            }
            else
            {
                update((x+y)/2+1,y,L,N,i);
            }
        }
    }
    

    叠放箱子问题

    某港口有一批箱子,将其编号,分别为1至N。每一个箱子的尺寸规格是一样的,现在要将其中某些箱子叠放起来,箱子叠放的规则如下:
    一、每个箱子上最多只能直接叠放一个箱子;
    二、编号较小的箱子不能放在编号较大的箱子之上;
    三、每个箱子都给出了自身重量与可承受重量,每个箱子之上的所有箱子重量之和不得超过该箱的可承受重量。
    为了节约堆放场地,希望你编程从中选出最多个箱子,使之能够在满足条件的情况下叠放起来。
    【输入】
    第一行是一个整数N(1≤N≤1000)。
    以下共有N行,每行两个整数,中间以空格分隔,分别表示每个箱子的自身重量与可承受重量,两个数值均为小于等于3000的正整数。
    【输出】
    第一行应当输出最多可叠放的箱子总数M。
    【样例】有五个箱子,如下表:
    1 19 15
    2 7 13
    3 5 7
    4 6 8
    5 1 2
    则最多可以叠放4个箱子,方案之一如:1、2、3、5

    思路

    倒序计算

    其余为0-1背包。

    代码

    #include <stdio.h>
    #include <stdlib.h>
    
    #define MAXNUM 1000//最大的箱子个数
    #define MAXWIGHT 3000//
    int n;//箱子数目
    int F[MAXNUM+1][6000];//第i个箱子到第n个箱子中总重量为j的最大箱子数
    int Weight[MAXNUM];//箱子重量
    int Capacity[MAXNUM];//箱子所能承受的压力
    
    int max(int ,int );
    //返回两个数的最大值
    
    int main()
    {
        int i,j,ans;
        printf("输入箱子的个数n(1-1000):\n");;
        scanf("%d",&n);
        printf("分别输入箱子的重量和能承受的重量(x y):\n");
        for(i=1; i<=n; i++)
            scanf("%d %d",&Weight[i],&Capacity[i]);
    
        F[n+1][0] = 0;
        for(i=n; i>=1; i--)
        {
            for(j=0; j<=2*MAXWIGHT; j++)
            {
                F[i][j]=F[i+1][j];
                if(j>=Weight[i]&&Capacity[i]>=j-Weight[i])
                {
                    F[i][j]=max(F[i][j],F[i+1][j-Weight[i]]+1);
                }
            }
        }
        ans=0;
        for(i=0; i<=6000; i++)
            ans = max(ans,F[1][i]);
        printf("最大叠放:%d",ans);
    
        return 0;
    }
    
    int max(int x,int y)
    {
        if(x>y)
            return x;
        else
            return y;
    }
    
    展开全文
  • poj经典动态规划题目解题报告

    热门讨论 2008-03-23 19:09:24
    poj经典动态规划题目解题报告,包括经典的动态规划题目20多道,可以作为学习动态规划系统的资料,包括题目: Pku acm 1179 Polygon Pku acm 1125 Stockbroker Grapevine Pku acm 1160 post office Pku ...
  • 经典动态规划题集资料不课错过哦 经典动态规划题集资料不课错过哦 经典动态规划题集资料不课错过哦
  • 经典的动态规划(就且成之为经典动态规划2) */ #include #define max(a,b) a>b?a:b using namespace std; int a[1000005],dp[1000005];//dp存储的是当前数值最优和.也就是最优解. int MAX(int n) { dp[1]=a[1]; ...
    /*
      NYoj 44 子串和
      经典的动态规划(就且成之为经典动态规划2)
    */
    #include<iostream>
    #define max(a,b) a>b?a:b
    using namespace std;
    int a[1000005],dp[1000005];//dp存储的是当前数值最优和.也就是最优解.
    int MAX(int n)
    {
        dp[1]=a[1];
        int Max=dp[1];
        for(int i=2;i<=n;i++)
        {
            dp[i]=max(dp[i-1]+a[i],a[i]);
            Max=max(dp[i],Max);
        }
        return Max;
    }
    int main()
    {
        int T;
        cin>>T;
        while(T--)
        {
            int n;
            cin>>n;
            for(int i=1;i<=n;i++)
            cin>>a[i];
            cout<<MAX(n)<<endl;
        }
    }
    

    展开全文
  • 经典动态规划问题--数字三角形 POJ--1163

    The Triangle

    Time Limit: 1000MS Memory Limit: 10000K
    Total Submissions: 35683 Accepted: 21357

    Description

    7
    3   8
    8   1   0
    2   7   4   4
    4   5   2   6   5
    
    (Figure 1)
    Figure 1 shows a number triangle. Write a program that calculates the highest sum of numbers passed on a route that starts at the top and ends somewhere on the base. Each step can go either diagonally down to the left or diagonally down to the right.

    Input

    Your program is to read from standard input. The first line contains one integer N: the number of rows in the triangle. The following N lines describe the data of the triangle. The number of rows in the triangle is > 1 but <= 100. The numbers in the triangle, all integers, are between 0 and 99.

    Output

    Your program is to write to standard output. The highest sum is written as an integer.

    Sample Input

    5
    7
    3 8
    8 1 0 
    2 7 4 4
    4 5 2 6 5

    Sample Output

    30

    解题思路:这道题目是动态规划的典型。其实递归,动态规划,分治从某种角度讲是十分的相近的。这个问题的子问题很明显是每次选择数字后对下一层的选择,每次都有两种。很容易想到用递归遍历每种解法,找到最大值。这种思路的好处是从上往下推,考虑比较正面。往往我们为了不超时间会开辟一个数组来存储我们已经计算得到的结果。也就是平常说的以空间换时间。

    下面是递归的写法:

    // 数字三角形问题.cpp : 定义控制台应用程序的入口点。
    //
    
    #include "stdafx.h"
    #include<iostream>
    #include<memory.h>
    #include<stdlib.h>
    #include<stdio.h>
    using namespace std;
    int a[110][110]={0};
    int record[110][110]={0};
    int n=0;
    int max_sum(int i,int j);
    int main()
    {
    	
    	while(scanf("%d",&n)!=EOF)
    	{
    		memset(record,-1,sizeof(record));
    		for(int i=0;i<n;i++)
    			for(int j=0;j<=i;j++)
    			    scanf("%d",&a[i][j]);
    		int sum=max_sum(0,0);
    		printf("%d",sum);
    	}
    	
    	return 0;
    }
    
    int max_sum(int i,int j)
    {
    	if(i==n-1)
    		return a[i][j];
    	int left=0,right=0;
    	if(record[i][j]==-1)
    	{
    		left=a[i][j]+max_sum(i+1,j);
    		right=a[i][j]+max_sum(i+1,j+1);
    		record[i][j]=left>right?left:right;
    	}
    	return record[i][j];
    }


    还有一种思考方式是从下往上推,具体来说就是假设轮到第i层的数字挑选他会从两个数字中和目前累计和最大的。

    看下面这个例子,总共5层,

    从第4层看。2会挑选5得到累加和7;7会挑选5得到累加和12;4会挑选6得到累加和10;下一个4会挑选6也得到10;

    再看第3层。8会挑选累加和较大的7,他的累加和是12,以此类推·······直到最后比较3和8的累加和谁大,7和其相加。

    7
    3   8
    8   1   0
    2   7   4   4
    4   5   2   6   5
    
    


     

    展开全文
  • 对于动态规划,每个刚接触的人都需要一段时间来理解,特别是第一次接触的时候总是想不通为什么这种方法可行,这篇文章就是为了帮助大家理解动态规划,并通过讲解基本的01背包问题来引导读者如何去思考动态规划。...
  • 动态规划实现实例:装配线问题。经典中的经典
  • 经典动态规划问题--最长上升子序列 POJ--2533

    Longest Ordered Subsequence

    Time Limit: 2000MS Memory Limit: 65536K
    Total Submissions: 30869 Accepted: 13465

    Description

    A numeric sequence of ai is ordered if a1 < a2 < ... < aN. Let the subsequence of the given numeric sequence ( a1, a2, ..., aN) be any sequence ( ai1, ai2, ..., aiK), where 1 <= i1 < i2 < ... < iK <= N. For example, sequence (1, 7, 3, 5, 9, 4, 8) has ordered subsequences, e. g., (1, 7), (3, 4, 8) and many others. All longest ordered subsequences are of length 4, e. g., (1, 3, 5, 8).

    Your program, when given the numeric sequence, must find the length of its longest ordered subsequence.

    Input

    The first line of input file contains the length of sequence N. The second line contains the elements of sequence - N integers in the range from 0 to 10000 each, separated by spaces. 1 <= N <= 1000

    Output

    Output file must contain a single integer - the length of the longest ordered subsequence of the given sequence.

    Sample Input

    7
    1 7 3 5 9 4 8

    Sample Output

    4
    

    解题思路:这一题刚开始有点卡住了,可能最近相同类型的题目做的有点多。最后看了提示想到的方法,不用递归去做。原题中要我们求解最大上升子序列,那么我们可以把问题分解为以求第 i 个数为结尾的子序列的最大上升子序列。而第i个数的解和前面i-1个数的解是存在联系的,这就是解题的核心。知道前面i-1个数的解后来求第i个数,我们只要和前面i-1个数相比找到比第i个数小且其解最大的值max,max+1就是第i个数的解!

     

    // 最长上升子序列.cpp : 定义控制台应用程序的入口点。
    //
    
    #include "stdafx.h"
    #include<iostream>
    #include<stdlib.h>
    #include<stdio.h>
    #include<memory.h>
    using namespace std;
    int a[1010]={0};
    int len_[1010]={0};
    
    int main()
    {
    	int n=0;
    	int max_=0;
    	while(scanf("%d",&n)!=EOF)
    	{
    		int i=0;
    		max_=0;
    
    		memset(a,0,sizeof(a));
    		for(i=0;i<n;i++)
    		{
    			scanf("%d",&a[i]);
    			len_[i]=1;
    		}
    		for(i=1;i<n;i++)
    		    for(int j=0;j<i;j++)
    				  if(a[i]>a[j])
    				  {
    					  len_[i]=max(len_[j]+1,len_[i]);
    				  }
    					 
    	
    		for(i=0;i<n;i++)
    			if(len_[i]>max_)
    				max_=len_[i];
    		printf("%d\n",max_);
    		
    	}
    	return 0;
    }
    
    


     

    展开全文
  • 经典动态规划2. 再次写这个题是时候,差不多没有调试就A了. 小有成就感. 思路:子串和就相当于该问题的一个子问题. 将行进行组合就可以了. */ #include #include #define max(a,b) a>b?a:b int MAX(int a[],int ...
  • 包括 导弹拦截 城市交通 数塔 数码称重 最短路径 mod 4 最优路径 骑士游历 方格取数 装箱问题 卡车更新问题 统计单词个数
  • 经典动态规划题:最大子序和

    万次阅读 2020-09-30 21:16:35
    给定一个整数数组nums,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。 示例: 输入: [-2,1,-3,4,-1,2,1,-5,4... 动态规划:定义dp[i]表示为nums[i]为结尾的[连续子数组的最大和] ...
  • 经典动态规划:高楼扔鸡蛋

    千次阅读 2019-11-18 12:15:00
    点击蓝色“五分钟学算法”关注我哟加个“星标”,天天中午 12:15,一起学算法作者 | labuladong来源 | labuladong今天要聊一个很经典的算法问题...具体的问题等会再说,但是这道题的解法技巧很多,光动态规划就好几...
  • 8.徐源盛《对一类动态规划问题的研究》 背包九讲Pack 【专辑】插头DP 【专辑】单调队列+斜率优化的DP 01背包问题 acm动态规划总结 PKU——DP专辑 背包之01 POJ 动态规划总结 背包之01背包、完全背包、多重背包详解 ...
  • 经典动态规划————背包九讲

    千次阅读 2017-02-20 16:24:58
    前言 本篇文章是我(dd_engi)正在...背包问题是一个经典动态规划模型。它既简单形象容易理解,又在某种程度上能够揭示动态规划的本质,故不少教材都把它作为动态规划部分的第一道例题,我也将它放在我的写作计划
  • 动态规划学习-【0-1背包问题的优化和变种】,地址:https://blog.csdn.net/program_developer/article/details/86488257 7. Balanced Partition 【1】 8. Edit Distance 【1】 9. Cunting Boolean...
  • 经典动态规划算法题(Java实现)

    千次阅读 2019-05-01 12:08:08
    待更新
  • 扔鸡蛋问题-经典动态规划问题

    千次阅读 2018-08-29 16:47:51
    //(1)动态规划法: 该算法的空间复杂度是O(nk),时间复杂度是O(nk^2) n表示鸡蛋数,k代表楼层数 public static int dropEggs ( int eggs, int floors) { //第一步永远是创建动态规划的备忘录,也叫状态...
  • 双调欧几里得旅行商问题是一个经典动态规划问题。《算法导论(第二版)》思考题15-1和北京大学OJ2677都出现了这个题目。 旅行商问题描述:平面上n个点,确定一条连接各点的最短闭合旅程。这个解的一般形式为NP的...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 44,964
精华内容 17,985
关键字:

经典动态规划