动态规划-（基本知识总结）_在一条呈直线的公路两旁有n个位置

总结：思维导图如下： 

 

以题为启：

        

 

         数字三角形问题：给定一个有n行数字组成的数字三角形，如上图所示。尝试设计一个算法，计算出从三角形的顶至底的一条路径，使得该路径经过的数字总和最大。

输入：5                                 输出：

7                                                 30

3 8

8 1 0

2 7 4 4

4 5 2 6 5

首先我们考虑，我们能不能使用暴力方法来解决这个问题。好像是可以，比如说我们从7开始，进行遍历，将每次遍历的值保存下来。第二行有两种选择，第三行有三种选择，以此类推，时间复杂度是n！。时间性能很差，要考虑更精巧的算法。我们在做求最优值的题目的时候，要考虑我们的动态规划能不能处理，或者说，我能不能转化成动态规划进行处理。接下来我们根据该题目进行对于动态规划的分析。

根据学习课程可知：

求解动态规划题目分为四个步骤：

1.判断最优子结构。

2.写出状态转移方程。

3.求解最优值。

4.构建最优解。

  对于这个题，看是否具有最优子结构；我们取倒数第二层的7，那它能得到的最大值一定是5，假设我们有一个更好的数为x，则x+7一定>7+5;这与初始条件相悖，我们可以一层一层向上推进，可以看出，全局的最大值，是我们自底向上一层一层求出来的，可以看出该问题满足最优子结构。

  确定该问题为最优子结构，状态转移方程就可以变得简单了，因为我们分析最优字结构的时候，我们就已经描述我们求解的过程，将描述代码化就可以了，状态转移方程为：

dp[i,j]=max{dp[i-1,j]+dp[i,j],dp[i-1,j+1]+dp[i,j]};

dp[0,j]=dian[0,j],0<=j<n;

dp[i,j]意思就是当前的值加上上方的数与加上右上方的数比较取得最大值。我们来看一小段代码：

for(int i=1;i<=n;i++){
        for(int j=0;j<=n-i;j++){
            max=jieguo[i-1][j]+dian[i][j];//对max进行初始化，初始化的值为当前的值加上左上方的值，如果当前值加上右上方的值比max要大，我就要取右上方的值，这就是状态转移方程的第一个式子。
            if(max<(jieguo[i-1][j+1]+dian[i][j]))
                {jieguo[i][j]=jieguo[i-1][j+1]+dian[i][j];}
            else{
                jieguo[i][j]=max;
            }
        }
    }

 以上代码就是实现状态转移方程的代码，最后得到的最优值是在jieguo【n】【0】；

要是想要构造最优解，我们就需要再开一个数组，保存我每次选择的位置，倒推回去输出即可。

我们再来看一个一维的动态规划的问题：

商店选址问题：在一条呈直线的公路两旁有n个位置x1, x2,…xn可以开商店,在位置xi处开商店的预期收益是pi，i=1,2,… n.如果任何两个商店之间的距离必须至少为d，那么如何选择开设商店的位置使得总收益达到最大？

输入：5 2                                                                         输出：21

每个可以开店的位置：1 4 6 7 9                                    1 4 6 9

每个开店位置的价值：5 6 7 4 3

在这里我们证明最优子结构的时候使用的是剪切法（cut&paste）

设x1,x2,....xn为原问题的最优解

则x1,x2,....x(n-1)为子问题的最优解

假设y1,y2,....y(n-1)为子问题的更优解

则y1,y2,....y(n-1),xn比x1,x2,....xn更优，与初始值相矛盾（因为我们已经确定一开始x1~xn为最优解了）。 故满足最优子结构。

接下来我们就寻找状态转移方程，我们从一号位置开始遍历，一号位置是小于d的，我们可以直接把该位置的价值与上一位置价值比较，如果小，就保存上一位置，这是小于d的情况。大于d的情况就是判断该位置减去d的时候位置的价值加上自身的价值与上一位置进行比较，取最大值。在求解的过程中我们可以发现，当在七号位置的时候，7-d是5，我们没有这个位置，我们可以直接扩展出这个位置，让这个位置的价值为0即可，这样方便我们进行解题。下面是状态转移方程：

dp[i]=max{dp[i-d]+v[i],dp[i-1]}, i>d;

dp[i]=max{dp[i-1],v[i]},i<d;

代码如下：

 for(int i=1;i<d+1;i++){//这个循环处理i<d
            if(b[i]<jieguo[i-1]) jieguo[i]=jieguo[i-1];
            else{
             jieguo[i]+=b[i];
            }
    }
    for(int i=d+1;i<=z;i++){//这个循环处理i>=d
        int max=jieguo[i-1];
        int temp=jieguo[i-d]+b[i];
        jieguo[i]=max>temp?max:temp;
    }
    return max;

最优解则是在结果数组中最大的那个数，而不是最后一个数。

构造最优解的时候，我们还是保存下来他的上一个是谁，求解过程就是判断该数是不是比前边那个数大，如果大说明该数在我的最优解中，打印出来，减去该数的价值，以此类推，就能构造出最优解；代码如下：

    int m=z;//z是该条公路是多长
    int dayin[z];
    int cnt1=0;
    while(m>=1){
        if(jieguo[m-1]>max){//大于时不用处理，说明我的最优解过程不会经历这个位置。
            m--;
            continue;
        }
        if(jieguo[m-1]!=max){
           dayin[cnt1++]=m;
            max-=b[m];
        }
        m--;
    }
    for(int j=cnt1-1;j>=0;j--) printf("%d ",dayin[j]);

最后一类就是相对较为复杂的题目，这种题目就是我们不能直接找出他的状态转移方程，我们要通过一些方法，转化出状态转移方程。我们来看下面这个题：求最长递增子序列的长度问题。

求一个字符串的最长递增子序列的长度。单调递增子序列

如：dabdbf最长递增子序列就是abdf，长度为4

输入

第一行一个整数0<n<20,表示有n个字符串要处理
随后的n行，每行有一个字符串，该字符串的长度不会超过10000

输出

输出字符串的最长递增子序列的长度

样例输入                                           样例输出

3

aaa                                                    1

ababc                                                3

abklmncdefg                                    7

我们通过案例可以发现，比如说abklmnc的最优解为abklmn而整体最优解为abcdefg，这很显然不满足最优子结构，所以我们要构造最优子结构，构造方法为每次保存以该位置元素为结尾的最大长度，最后遍历取最大值。状态转移方程为：dp[i]=dp[j]<dp[i]，j<i&&b[j]+1>b[i];

b数组是保存以该位置元素为结尾的最大长度，保证b[j]+1>b[i]是因为比如ababcb这种情况到c的时候应该是abc而不是ababc这样会导致答案错误。

求最优解代码如下：

for(int i=0;i<len;i++){
        b[i]=1;
        for(int j=0;j<i;j++){
            if(a[j]<a[i]&&b[j]+1>b[i]){
                b[i]=b[j]+1;
            }
        }
    }

最后经典案例就是01背包问题了，这里就简述思路，因为状态转移方程出来，代码也就实现了，问题描述：有 N 个物品和容量为 W 的背包，每个物品都有自己的体积 w 和价值 v，求拿哪些物品可以使得背包所装下物品的总价值最大。如果限定每种物品只能选择 0 个或 1 个，则问题称为 0-1 背包问题；

我们的思路就是这个物品加入进去得到的价值与没加入进去的价值进行比较取最大值。状态转移方程为：

dp[i,j]=max{dp[i-1,j-wi]+v[i],dp[i-1,j]，j>=w；

 dp[i,j]=dp[i-1,j]，j<w;

实现代码为：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int w[999];
int v[999];
int jieguo[999][999];
int s[999];
int f(int n,int c){
    for(int i=1;i<=n;i++){
        for(int j=1;j<=c;j++){
            if(w[i]>j) jieguo[i][j]=jieguo[i-1][j];
            else {
                int max=jieguo[i-1][j-w[i]]+v[i];
                jieguo[i][j]=max>jieguo[i-1][j]?max:jieguo[i-1][j];
            }
        }
    }
    return jieguo[n][c];
}
int main()
{
    int n,c;
    scanf("%d%d",&n,&c);
    for(int i=1;i<=n;i++){
        scanf("%d",&v[i]);
    }
    for(int i=1;i<=n;i++){
        scanf("%d",&w[i]);
    }
    int answer=f(n,c);
    printf("%d\n",answer);
    int r=c;
    int l=n;
    while(r&&l){
        if(jieguo[l][r]==jieguo[l-1][r]){
            l--;
            continue;
        }
        else{
            s[l]=1;
            r=r-w[l];
            l--;
        }
    }
    for(int i=1;i<=n;i++){
        printf("%d ",s[i]);
    }
    return 0;
}

求最优值的过程就是如果jieguo[i][j]!=jieguo[i-1][j];就说明包含了这个物品，然后减去该物品的价值，与商店选址求最优解类似。