动态规划总结

---恢复内容开始---

动态规划来源于分治法,本质是为了节省递归栈所消耗的时间/空间,同时把相同的子问题的解记录下来,防止系统做重复工作,浪费时间。

一般用动态规划做题时候,要从分治法开始,进一步考虑是否存在相同的子问题解且解是否重复,如果有可以采用动态规划求解【当然递归方程还是要写的】。

动态规划的递归方程和分治法略有不同,动态规划的递归一般都用二维数组储存数据【当然也有用一维数组甚至一个变量的,不过都是二维数组的简化版】,首先我们要弄清楚m[i][j]的几何意义,然后根据题目要求写出m[i][j]=...【一般都是和m其他元素挂钩的】,这就是动态规划的递归方程。

一般写递归方程分为以下几种情况

1.确定规划起点终点,规划方向确定

例题:

7-1 数字三角形 (30 分)
 

给定一个由 n行数字组成的数字三角形如下图所示。试设计一个算法,计算出从三角形 的顶至底的一条路径(每一步可沿左斜线向下或右斜线向下),使该路径经过的数字总和最大。

QQ截图20170929023616.jpg

输入格式:

输入有n+1行:

第 1 行是数字三角形的行数 n,1<=n<=100。

接下来 n行是数字三角形各行中的数字。所有数字在0..99 之间。

输出格式:

输出最大路径的值。

输入样例:

在这里给出一组输入。例如:

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

输出样例:

在这里给出相应的输出。例如:

30

一般遇到这种题只需要从终点入手,就会发现到终点的路径值只能是m[i-1][j]或者m[i-1][j-1]再加自己的值,这样子到终点问题就被转化成为了到达倒数第二层格子的值,以此类推。

#include<iostream>
using namespace std;

int main()
{
    int n,i,j;
    cin>>n;
    int a[101][101];
    int d[101][101];
    for(i=1;i<101;i++)
    {
        for(j=1;j<101;j++)
        {
            a[i][j]=0;
        }
    }
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=i;j++)
        {
            cin>>a[i][j];
        }
    }

    for(j=1;j<=n;j++)
    {
        d[n][j]=a[n][j];
    }
    for(i=n-1;i>=1;i--)
    {
        for(j=1;j<=n;j++)
        {
            if(d[i+1][j]>d[i+1][j+1])
            {
                d[i][j]=d[i+1][j]+a[i][j];
            }
            else
            {
                d[i][j]=d[i+1][j+1]+a[i][j];
            }
        }
    }
    cout<<d[1][1];
}

当然不创建d数组而直接覆盖a数组也是可以的

结论:这种确定方向的题,从终点把每个情况想清楚,然后得出最大最小即可。

其他问题:商人过路费,求子段最小操作数问题

2.方向不确定或者自由,起终点确定:

3-2 租用游艇问题 (22 分)
 

题目来源:王晓东,《算法设计与分析》

长江游艇俱乐部在长江上设置了n个游艇出租站1,2,…,n。游客可在这些游艇出租站租用游艇,并在下游的任何一个游艇出租站归还游艇。游艇出租站i到游艇出租站j之间的租金为r(i,j),1<=i<j<=n。试设计一个算法,计算出从游艇出租站1 到游艇出租站n所需的最少租金。

输入格式:

第1 行中有1 个正整数n(n<=200),表示有n个游艇出租站。接下来的第1到第n-1 行,第i行表示第i站到第i+1站,第i+2站, ... , 第n站的租金。

输出格式:

输出从游艇出租站1 到游艇出租站n所需的最少租金。

输入样例:

在这里给出一组输入。例如:

3
5 15
7

输出样例:

在这里给出相应的输出。例如:

12

这道题同样从终点想到起点,从i到n,要么直接过去,要么经过一堆中途站,而这些中途站所在值可以作为子问题求解。

递归方程:m[i][j]从第i个站出发到j=max(m[i][k]+m[k][j],m[i][j])其中k<n,大于y一般都用for循环求出结果。

#include<iostream>
using namespace std;
int main()
{
    int n,i,j,k;
    int yangtzeriver[200][200];
    cin>>n;
    for(i=0;i<n;i++)
    {
        yangtzeriver[i][i]=0;
        
    }
    for(i=0;i<n;i++)
    {
        for(j=i+1;j<n;j++)
        {
            cin>>yangtzeriver[i][j];
            
        }
    }
    //cout<<"e";
    for(i=n-1;i>=0;i--)
    {
        //cout<<" d";
        for(j=i+1;j<n;j++)
        {
            //cout<<yangtzeriver[i][j]<<" "<<(yangtzeriver[i][j-1]+yangtzeriver[j-1][j]);
            
            int mini=min(yangtzeriver[i][j],yangtzeriver[i][j-1]+yangtzeriver[j-1][j]);
            for(k=i+1;k<j;k++)
            {
                int q=min(yangtzeriver[i][j],yangtzeriver[i][k]+yangtzeriver[k][j]);
                //cout<<yangtzeriver[i][j]<<" "<<(yangtzeriver[i][k]+yangtzeriver[k][j])<<" ";
                if(q<mini)
                {
                    mini=q;
                }
            }
            //cout<<mini;
            yangtzeriver[i][j]=mini;
        }
    }
    cout<<yangtzeriver[0][n-1];

如:3-1,3-3

3.方向确定,起终点不自由

一般采用方法是记录最大值

如:

3-2 租用游艇问题 (22 分)
 

题目来源:王晓东,《算法设计与分析》

长江游艇俱乐部在长江上设置了n个游艇出租站1,2,…,n。游客可在这些游艇出租站租用游艇,并在下游的任何一个游艇出租站归还游艇。游艇出租站i到游艇出租站j之间的租金为r(i,j),1<=i<j<=n。试设计一个算法,计算出从游艇出租站1 到游艇出租站n所需的最少租金。

输入格式:

第1 行中有1 个正整数n(n<=200),表示有n个游艇出租站。接下来的第1到第n-1 行,第i行表示第i站到第i+1站,第i+2站, ... , 第n站的租金。

输出格式:

输出从游艇出租站1 到游艇出租站n所需的最少租金。

输入样例:

在这里给出一组输入。例如:

3
5 15
7

输出样例:

在这里给出相应的输出。例如:12

一般遇到这种题,就不要把思维局限在终点。要这样想:从任意一个数开始,如果前面一堆数<0,
那以他为底的尾串就是自己,否则是前面一堆数加上这个数得到递归方程m[j]=max(m[j-1]+num[j],num[j]),
或者if num[j]<0,m[j]=num[j],else m[j]=(m[j-1]+num[j])
代码省略 自己看书
//看书
 
      
(当然 直接分治法方法加备忘录 也是可以的)

4.都没有 自己挑 如0-1背包
0-1背包:给定种物品和一个容量为的背包,物品的重量是,其价值为,背包问题是如何使选择装入背包内的物品,使得装入背包中的物品的总价值最大。其中,每种物品只有全部装入背包或不装入背包两种选择。
这种题目二维数组的代表意义会十分的奇怪,比如说在0-1背包中,一个数代表从几号物品开始装,另一个数代表容量。
把二维数组顺序搞明白后,就会明显发现m[i][j]=max(m[i+1][j-i的价值],m[i+1][j])【前提:能装的下(j>i的价值),装不下直接m[i+1][j]】
然后把最后一行填好,就能往上填表了


#include<iostream>
using namespace std;
int main()
{
    int n,capity,i,j;
    cin>>n>>capity;
    int item[100],percapity[100];
    for(i=0;i<n;i++)
    {
        cin>>item[i];
        cin>>percapity[i];
    }
    int bag[100][100];
    for(j=0;j<=capity;j++)
    {
        if(j<percapity[n-1])
        {
            bag[n-1][j]=0;
        }
        else bag[n-1][j]=percapity[n-1];
    }
    for(i=n-2;i>=0;i--)
    {
        for(j=1;j<=capity;j++)
        {
            if(j>=percapity[i])
            {
                bag[i][j]=max(bag[i+1][j],bag[i+1][j-percapity[i]]+item[i]);
            }
            else bag[i][j]=bag[i+1][j];
        }
    }
    cout<<bag[0][capity];
}
 
      

一般情况下,我们可以根据表之前的结果得到m[i][j]的结果,通常需要比较i,j和递归式里面i,j的关系,从而得到i和j在填表for循环里面的顺序,从而求i和j究竟递增,还是递增。一般递归式里面i比原i大递减,否则递增,j同理。

相关文章
相关标签/搜索