动态规划入门

基本思想

基本思想与分治法类似，也是将待求解的问题分解为若干个子问题(阶段)，按顺序求解子阶段，前一子问题的解，为后一子问题的求解提供了有用的信息。在求解任一子问题时，列出各种可能的局部解，通过决策保留那些有可能达到最优的局部解，丢弃其他局部解。依次解决各子问题，最后一个子问题就是初始问题的解
与分治法最大的差别是：
适合于用动态规划法求解的问题，经分解后得到的子问题往往不是互相独立的，即下一个子阶段的求解是建立在上一个子阶段的解的基础上，进行进一步的求解

求解的基本步骤

初始状态→│决策１│→│决策２│→…→│决策ｎ│→结束状态
1.划分阶段：按照问题的时间或空间特征，把问题分为若干个阶段。
2.确定状态和状态变量：将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来
3.确定决策并写出状态转移方程：因为决策和状态转移有着天然的联系，状态转移就是根据上
一阶段的状态和决策来导出本阶段的状态
4.寻找边界条件：给出的状态转移方程是一个递推式，需要一个递推的终止条件或边界条件

实际应用中的步骤进行设计

1.分析最优解的性质，并刻画其结构特征。
2.递归的定义最优解。
3.以自底向上或自顶向下的记忆化方式(备忘录法)计算出最优值
4.根据计算最优值时得到的信息，构造问题的最优解

Hdu 1003 Max Sum

链接

Max Sum

题意

给定长度为n的数列,求最大子序列和

分析

求一个子区间它的和最大,dp[i]为子区间[k,i] (1<=k<=i) 最大和
若dp[i-1]<0，dp[i]=a[i]，否则 dp[i]=dp[i-1]+a[i]

代码

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
const int N=100000;
const int INF=0x3f3f3f3f;
int main(){

    int T,n;
    scanf("%d",&T);
    for(int k=1;k<=T;k++){
        scanf("%d",&n);
        int x,ansl,ansr,l=1,r=1,sum=0,ans=-INF;
        for(int i=1;i<=n;i++){
            scanf("%d",&x);
            r=i;
            if(sum<0){
                sum=x;
                l=i;
            }
            else
                sum+=x;
            if(sum>ans){
                ans=sum;
                ansl=l;
                ansr=r;
            }
        }
        printf("Case %d:\n%d %d %d\n",k,ans,ansl,ansr);
        if(k!=T) printf("\n");
    }
    return 0;
}

POJ 1050 To the Max

链接

To the Max

题意

给定一个n*n的矩阵，求最大子矩阵和

分析

最大子序列和的拓展，由一维变成了二维，可以转化为求最大子序列和
最大子矩阵肯定是[a,b]行[c,d]列的和，
可以先求出[a,b]行[1,n]列的和再用最大子序列和求解
dp[k]为[i,j]行第k列的和,所有的[i,j]行的最大子序列和的最大值即为答案

代码

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
const int N=105;
const int INF=0x3f3f3f3f;
int n,a[N][N],dp[N];
int maxSum(){

    int maxs=-INF,sum=0;
    for(int i=1;i<=n;i++){
        if(sum<0)
            sum=dp[i];
        else
            sum+=dp[i];
        maxs=max(maxs,sum);
    }
    return maxs;
}
int main(){

    while(scanf("%d",&n)!=EOF){
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                scanf("%d",&a[i][j]);
        int ans=-INF;
        for(int i=1;i<=n;i++){
            memset(dp,0,sizeof(dp));
            for(int j=i;j<=n;j++){ //从第i行到第j行
                for(int k=1;k<=n;k++)
                    dp[k]+=a[j][k];  //dp[k]为第k列的和
                ans=max(ans,maxSum());
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}

POJ 1164 放苹果

链接

放苹果

题意

把M个同样的苹果放在N个同样的盘子里，允许有的盘子空着不放，
问共有多少种不同的分法？5，1，1和1，5，1 是同一种分法

分析

dp[i][j]表示将i个苹果放入j个盘中的方法数
i<j时,最多用i个盘子就可以,即dp[i][j]=dp[i][i]
$i \geqslant j$时,有两种情况,
1.至少有一个盘中为空，则有dp[i][j-1]种方法
2.所有盘中都不空,则每个盘子至少有一个苹果,即先将每个盘放一个苹果
再将剩下的i-j个苹果放入j个盘中,有dp[i-j][j]种方法

状态转移方程

$i<j,dp[i][j]=dp[i][i]$
$i \geqslant j,dp[i][j]=dp[i][j-1]+dp[i-j][j]$

代码

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
const int N=10;
const int INF=0x3f3f3f3f;
int dp[N+5][N+5];
void solve(){

    for(int i=1;i<=N;i++){
        dp[i][0]=dp[0][i]=1;
        dp[i][1]=dp[1][i]=1;
    }
    for(int i=2;i<=N;i++){ //苹果
        for(int j=2;j<=N;j++){ //盘子
            if(i<j)
                dp[i][j]=dp[i][i];
            else
                dp[i][j]=dp[i][j-1]+dp[i-j][j];
        }
    }
}
int main(){

    int n,m,T;
    solve();
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&m,&n);
        printf("%d\n",dp[m][n]);
    }
    return 0;
}

Hdu 1158 Employment Planning

链接

Employment Planning

题意

一个项目需要n个月完成，给定每个月所需要的工人的最小人数，
以及雇佣一个工人的花费hir，一个工人一个月的薪水sal，解雇一个工人的花费fir
每个工人的hir,sal,fir分别相同，求完成整个工程所需的最小花费

分析

雇佣一个工人的花费只在雇佣时花一次钱，解雇也是
只要雇佣了某个工人，就算工人不做事，每个月也得付薪水
dp[i][j]表示第i个月后，雇佣了j个工人所需的最小费用
dp[i][j]=min(dp[i-1][k]+j个人的薪水+解雇k-j人的花费或者雇佣j-k人的花费)
若这n个月所需工人的最大值为maxNum
则最多雇佣maxNum个工人，因为每个工人都需要薪水，
雇佣的人数比最大的需求值更大只会多花钱

参考代码

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
const int INF=0x3f3f3f3f;
int n,maxNum,hir,sal,fir,num[15],dp[15][1010];
int solve(){

    memset(dp,INF,sizeof(dp));
    for(int i=num[1];i<=maxNum;i++)
        dp[1][i]=hir*i+sal*i;
    for(int i=2;i<=n;i++)
        for(int j=num[i];j<=maxNum;j++){
            for(int k=num[i-1];k<=maxNum;k++){
                if(j<=k) //需解雇k-j人
                    dp[i][j]=min(dp[i][j],dp[i-1][k]+j*sal+(k-j)*fir);
                else    //需雇佣j-k人
                    dp[i][j]=min(dp[i][j],dp[i-1][k]+j*sal+(j-k)*hir);
            }
        }
    int ans=INF;
    for(int i=num[n];i<=maxNum;i++)
        ans=min(ans,dp[n][i]);
    return ans;
}
int main(){

    while(scanf("%d",&n)&&n){
        scanf("%d%d%d",&hir,&sal,&fir);
        for(int i=1;i<=n;i++){
            scanf("%d",&num[i]);
            maxNum=max(maxNum,num[i]);
        }
        printf("%d\n",solve());
    }
    return 0;
}