算法整理六——动态规划

一、概述

• 基本思想是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。
• 动态规划算法的有效性依赖于问题本身所具有的两个重要性质：最优子结构、重叠子问题

1、最优子结构：当问题的最优解包含了其子问题的最优解时，称该问题具有最优子结构性质。

2、重叠子问题：

在解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。动态规划算法(自底向上)正是利用了这种子问题的重叠性质，对每一个子问题只解一次，而后将其解保存在一个表格中，在以后尽可能多地利用这些子问题的解。

• 动态规划算法，对每一个子问题只解一次，而后将其解保存在一个表格中，当再次需要解此子问题时，只是简单地用常数时间查看一下结果。
• 动态规划算法是分阶段决策，最终使整个过程达到最好的决策。得到的是全局最优解。
• 各个阶段决策的选取不是任意确定的，它依赖于当前面临的状态，又影响以后的发展。
• 动态规划算法的四个基本步骤

1. 找出最优解的性质，并刻画其结构特征；
2. 递归地定义最优值（写出动态规划方程）；
3. 以自底向上的方式计算出最优值；
4. 根据计算最优值时得到的信息，构造一个最优解（自顶向下，递归）。

其中，步骤1～3是动态规划算法的基本步骤。在只需要求出最优值的情形，步骤4可以省略；若需要求出问题的一个最优解，则必须执行步骤4。

3、备忘录方法是动态规划算法的变形。

4、与动态规划算法一样，备忘录方法用一个表格保存已解决的子问题的答案，再碰到该子问题时，只要简单地查看该子问题的解答，而不必重新求解。

5、与动态规划算法不同的是，备忘录方法采用的是自顶向下的递归方式，而动态规划算法采用的是自底向上的非递归方式。

6、备忘录方法的控制结构与直接递归方法的控制结构相同，区别仅在于备忘录方法为每个解过的子问题建立了备忘录以备需要时查看，避免了相同子问题的重复求解（减少了递归调用的次数，提高运行效率）。

7、关于动态规划算法和备忘录方法的适用条件

• 一般来说，当一个问题的所有子问题都至少要解一次时，用动态规划算法比用备忘录方法好。
• 当子问题空间中部分子问题可以不必求解时，易用备忘录方法则较为有利，因为从其控制结构可以看出，该方法只解那些确实需要求解的子问题。
• 两者可以解决同一问题，并且两者的时间复杂度一样（教材P90 了解）

8、用动态规划和备忘录方法分别解决：矩阵连乘积问题

9、用分治法和动态规划法分别解决最大子段和问题（第四步求最优解不需要掌握）

10、用动态规划法解决0-1背包问题、最长单调递增子序列、最长公共子序列（会写出计算最长公共子序列长度的递推式即可）、数字三角形问题、点菜（openjudge题目）

二、矩阵连乘积问题

分析：

矩阵相乘的条件：第一个矩阵的列数=第二个矩阵的行数。

矩阵连乘次数=第一个矩阵行数*第一个矩阵列数*第二个矩阵列数*第三个矩阵列数*....*第n个矩阵的列数

1. 分析最优解的结构

将矩阵连乘积AiAi+1…Aj 简记为A[i:j], 这里i≤j;

特征：计算A[1:n]的最优次序所包含的计算矩阵子链 A[1:k]和A[k+1:n]的次序也是最优的。

1. 建立动态规划方程

则其相应完全加括号方式为(A1A2…Ak)(Ak+1Ak+2…An)

计算量（乘法计算的次数）=：

A[1:k]的计算量+

A[k+1:n]的计算量+

A[1:k]和A[k+1:n]相乘的计算量

设计算A[i: j]（1≤i≤j≤n）所需要的最少乘法次数为m[i][j]，则原问题的最优值为m[1][n]

• 当i=j时，A[i: j]=Ai，因此，m[i][i]=0，
• 当i<j 时，m[i][j]=m[i][k]+m[k+1,j]+Pi-1PkPj

(Ai的维数是Pi-1×Pi),k的位置只有 j-i 种可能

3、计算最优值

动态规划算法

 

#include<iostream>
 
#include<algorithm>
 
#include<cstdio>
 
using namespace std;
 
int p[11];
 
int m[101][101];//记录子问题的最优值,最少乘法次数
 
int s[101][101];//记录子问题的最优解
 
void Maxs(int n)
 
{
 
    for(int i=1;i<=n;i++)
 
        m[i][i]=0;//长度是1的矩阵链连乘的计算次数
 
    for(int r=2;r<=n;r++)//矩阵链的长度，按照矩阵链长度递增的方法完成计算
 
        for(int i=1;i<=n-r+1;i++)//连乘的起点
 
    {
 
        int j=i+r-1;//矩阵链中的最后一个矩阵的编号
 
        m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j];//m[i][j]的假设值
 
        s[i][j]=i;//断开位置的初值，记录即最优解的初值
 
        for(int k=i+1;k<j;k++)
 
        {
 
            int t=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];
 
            if(t<m[i][j])
 
            {
 
                m[i][j]=t;
 
                s[i][j]=k;
 
            }
 
        }
 
    }
 
}
 
void printM(int m[101][101], int n)
 
{
 
int i,j;
 
for(i = 1; i <= n; i++)
 
{
 
for(j = 1; j <= n; j++)
 
{
 
printf("%d\t",m[i][j]);
 
}
 
printf("\n");
 
}
 
}
 
 
 
void printS(int s[101][101], int n)
 
{
 
int i,j;
 
for(i = 1; i <= n; i++)
 
{
 
for(j = 1; j <= n; j++)
 
{
 
printf("%d\t",s[i][j]);
 
}
 
printf("\n");
 
}
 
}
 
 
 
int main()
 
{
 
    int n;//矩阵个数
 
    cin>>n;
    for(int i=0;i<=n;i++)//每一个矩阵维数
 
    {
 
        cin>>p[i];
    }
 
    Maxs(n);
 
    printf("最少数乘次数矩阵 \n");
 
printM(m ,n);
 
printf("最佳断开位置矩阵 \n");
 
printS(s, n);
 
}

备忘录算法

int LookupChai  (int i, int j){
 
if (m[i][j]>0) return m[i][j];
 
if (i==j) return 0;
 
int u = LookupChain(i,i)+LookupChain(i+1,j)+p[i-1]*p[i]*p[j];
 
s[i][j] = i;
 
for (int k = i+1; k<j; k++) {
 
  Int  t = LookupChain(i,k)+LookupChain(k+1,j)+p[i-1]*p[k]*p[j];
 
  if (t < u) { u = t; s[i][j] = k;}
 
}
 
m[i][j] = u;
 
return u;
 
}

三、最大子段和问题

给定由n个整数（包含负整数）组成的序列a1,a2,...,an，求该序列子段和的最大值。

当所有整数均为负值时定义其最大子段和为0。

所求的最优值为：

 

例如：

当(a1,a2, ……a7,a8)=(1,-3, 7,8,-4,12, -10,6)时，
最大子段和为：

 

分治法

如果将所给的序列a[1:n]分为长度相等的两段a[1:n/2]和a[n/2+1:n]，分别求出这两段的最大子段和，则a[1:n]的最大子段和有三种情形：

• a[1:n]的最大子段和与a[1:n/2]的最大子段和相同；
• a[1:n]的最大子段和与a[n/2+1:n]的最大子段和相同；
• a[1:n]的最大子段和在两段中间

 

A、B这两种情形可递归求得。

对于情形C，容易看出，a[n/2]与a[n/2+1]同时在最优子序列中。因此，我们可以在a[1:n/2]和a[n/2+1:n]中分别计算出s1和s2。则s1+s2即为情形C的最优值。【即分别求两段的max，然后相加】

#include<iostream>
 
#include<algorithm>
 
#include<cstdio>
 
using namespace std;
 
int MaxSum(int a[],int left,int right)
 
{
 
    int sum=0;
 
    if(left==right)//终止条件
 
    {
 
        if(a[left]>0)
 
           sum=a[left];
 
        else
 
            sum=0;
 
    }
 
    else
 
    {
 
        //初始化
 
        int center=(left+right)/2;
 
        int lsum=MaxSum(a,left,center);
 
        int rsum=MaxSum(a,center+1,right);
 
        int s1=0,lefts=0;//lefts是左边的和,s1用来保存左边的和
 
        //左边
 
        for(int i=center;i>=left;i--)
 
        {
 
            lefts+=a[i];
 
            if(lefts>s1)
 
                s1=lefts;//这样s1保存的就是左边子段和最大值
 
        }
 
        int s2=0,rights=0;
 
        for(int i=center+1;i<=right;i++)
 
        {
 
            rights+=a[i];
 
            if(rights>s2)
 
                s2=rights;//s2保存的就是右边子段和最大值
 
        }
 
        sum=s1+s2;
 
        if(sum<lsum)
 
            sum=lsum;
 
        if(sum<rsum)
 
            sum=rsum;
 
    }
 
    return sum;
 
}
 
int main()
 
{
 
    int n=8,a[101]={1,-3, 7,8,-4,12, -10,6};
 
    cout<<MaxSum(a,1,n)<<endl;
 
}

动态规划法

设bj是以j结尾的区间的最大子段和(1~j,2~j,…j~j,共j个子段):

这样的话分别计算以1结尾的子段和的最大值、以2结尾的子段和的最大值、......

设a[i]表示以i结尾的最大子段和的最大值

当bj-1>0时，bj=bj-1+aj，

否则，bj=aj。

则计算bj的动态规划式：

bj=max{bj-1+aj，aj}，1≤j≤n。

#include<iostream>
 
#include<algorithm>
 
#include<cstdio>
 
using namespace std;
 
int MaxSum(int a[],int n)
 
{
 
    int sum=0;//最大子段和
 
    int b=0;//1~j的最大子段和，因无需保留其他结果，所以没必要定义数组
 
    for(int j=1;j<=n;j++)
 
    {
 
       if(b>0)//>0就加上
 
         b+=a[j];
 
       else    //<=0,就不用加
 
         b=a[j];
 
       if(b>sum)
 
            sum=b;
 
    }
 
    return sum;
 
}
 
int main()
 
{
 
    int n=8,a[101]={1,-3, 7,8,-4,12, -10,6};
 
    cout<<MaxSum(a,n)<<endl;
 
}

计算最大子段和的动态规划算法的最优解

令besti，bestj为最大子段和sum的起始位置和结束位置；

当b[i-1]≤0时，begin＝i；

当b[i]≥sum时，besti＝begin，bestj＝i。

int MaxSum(int a[],int n,int besti,int bestj)

{

    int sum=0;//最大子段和

    int b=0;//1~j的最大子段和，因无需保留其他结果，所以没必要定义数组

    int begin=0;

    for(int j=1;j<=n;j++)

    {

       if(b>0)//>0就加上

         b+=a[j];

       else    //<=0,就不用加

       {

           b=a[j];

           begin=j;

       }

       if(b>sum)

       {

           sum=b;

           besti=begin;

           bestj=j;

       }

    }

    cout<<besti<<"  "<<bestj<<endl;

    return sum;

}

四、0-1背包问题

给定一个物品集合s＝｛1，2，3，…，n｝，物品i的重量是wi，其价值是ci，背包的容量为m，即最大载重量不超过m。在限定的总重量m内，我们如何选择物品，才能使得物品的总价值最大。

如果物品不能被分割，即物品i要么整个地选取，要么不选取；不能将物品i装入背包多次，也不能只装入部分物品i，则该问题称为0-1背包问题。

如果物品可以拆分，则问题称为背包问题，适合使用贪心算法。

• 处理方案:

f[i][v]表示前 i 件物品(部分或全部)放入一个容量为 m 的背包可以获得的最大价值。（这时已处理完第 i 件物品，总重量不超过v）

         （1）某一物品w[i]>v的情况下，肯定不装入；

         （2）否则，根据

             max{f[i-1][v],f[i-1][v-w[i]]+c[i]}【不装入第i个物品，装入第i个物品】

         进行决策

• 状态转移方程:

     f[i][v]=max{f[i-1][v],f[i-1][v-w[i]]+c[i]}

#include<iostream>
 
#include<algorithm>
 
#include<cstdio>
 
using namespace std;
 
const int maxm = 201, maxn = 31;
 
int m, n;    int w[maxn], c[maxn];
 
int f[maxn][maxm];
 
int max(int x,int y)
 
{
 
    if(x>y)
 
        return x;
 
    else
 
        return y;
 
}
 
 
 
int main()
 
{
 
   cin>>m>>n;//背包容量m,物品数量n;
   for(int i=1;i<=n;i++)
 
      cin>>w[i]>>c[i];//每个物品的重量和价值
    for(int i=1;i<=n;i++)
 
        for(int v=m;v>=1;v--)
 
    {
 
        if(w[i]<=v)//v表示背包剩余容量
 
            f[i][v]=max(f[i-1][v],f[i-1][v-w[i]]+c[i]);
 
        else
 
            f[i][v]=f[i-1][v];
 
    }
 
    cout<<f[n][m]<<endl;//f[n][m]为最优解
 
    return 0;
 
}

五、最长单调递增子序列

设计一个O(n2)时间的算法, 找出由n个数组成的序列的最长单调递增子序列。

输入：

第1个整数n(0<n<100),表示后面有n个数据，全部为整数。

输出：

输出最长单调递增子序列的长度。

样例输入

8     65 158 170 155 239 300 207 389

样例输出

6

算法分析：

用数组b[i]记录以a[i] (1≤i<n) 为结尾元素的最长递增子序列的长度。

b[i] = max {b[k]} + 1   1≤k<i   a[k] ≤a[i]

代码：

#include<iostream>
 
#include<algorithm>
 
#include<cstdio>
 
using namespace std;
 
int a[101];
 
int MaxL(int n)
 
{
 
    int b[101]={0};//用数组b[i]记录以a[i] (1≤i<n) 为结尾元素的最长递增子序列的长度。
 
    int i,j;
 
    b[1]=1;//以a[1]结尾的子序列中只包含一个元素
 
    int max=1;//数组b的最大值
 
    for(i=2;i<=n;i++)
 
    {
 
        int k=0;//记录长度
 
        for(j=1;j<i;j++)
 
            if(a[j]<=a[i]&&k<b[j])
 
                k=b[j];
 
        b[i]=k+1;//求出以a[i]结尾的最长长度
 
        if(max<b[i])
 
            max=b[i];
 
    }
 
    return max;
 
}
 
int main()
 
{
 
   int n;
 
   cin>>n;
   for(int i=1;i<=n;i++)
 
   {
 
       cin>>a[i];
   }
 
   cout<<MaxL(n)<<endl;
 
}

六、最长公共子序列

若给定序列X={x1,x2,…,xm}，则另一序列Z={z1,z2,…,zk} 是X的子序列是指存在一个严格递增下标序列{i1,i2,…,ik}使得对于所有j=1,2,…,k有：zj=xij。

例如：

例如，序列Z={B，C，D，B}是序列X={A，B，C，B，D，A，B}的子序列，相应的递增下标序列为{2，3，5，7}。

题目：

给定2个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。

给定2个序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}，找出X和Y的最长公共子序列。

1、分析最优解的结构

设序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}的最长公共子序列为Z={z1,z2,…,zk} ，则

若xm=yn，则集合Z的特点:zk=xm=yn，且Zk-1是Xm-1和Yn-1的最长公共子序列。

若xm≠yn且，则Z的特点:是Xm-1和Y的最长公共子序列;或是X和Yn-1的最长公共子序列

2、建立递推关系

用c[i][j]记录序列Xi和Yj的最长公共子序列的长度。

• 当i=0或j=0时，c[i][j]=0；
• x[i]==y[j]，c[i][j]=c[i-1][j-1]+1
• x[i]!=y[j]，c[i][j]=max(c[i-1][j], c[i][j-1])

七、数字三角形问题

请编一个程序计算从顶到底的某处的一条路径，使该路径所经过的数字总和最大。只要求输出总和。

• 一步可沿左斜线向下或右斜线向下走；
• 三角形行数小于等于100；
• 三角形中的数字为0，1，…，99；

 

二维数组存储，格式如右图

f[x][y]表示从(1,1)到(x,y)的路径的最大权值和

这个题我们在前面用递推就做过了，以上的分析和前面都一样

递推的时候：

f[1][1]=a[1][1] 临界条件

f[x][y]=max{f[x-1][y]，f[x-1][y-1]}  递推式

最终答案求Ans=max{f[N][1],f[N][2],...,f[N][N]}

动态规划：【逆推法】

数字三角形用f[][]数组存储，表示数字三角形最后一行移动到  i行 j列位置的最大数字和

f[i][j]=f[i+1][j]+f[i][j]或者f[i][j]=f[i+1][j+1]+f[i][j]

f[i][j]=max(f[i+1][j],f[i+1][j+1])+f[i][j]

最终结果求f[0][0]

1、最优值：

#include<iostream>
 
#include<algorithm>
 
#include<cstdio>
 
using namespace std;
 
int f[101][101];
 
int ff(int n)
 
{
 
    int i,j;
 
    for(i=n-2;i>=0;i--)//从倒数第二行开始与倒数第一行加
 
    {
 
        for(j=0;j<=i;j++)
 
        {
 
            if(f[i+1][j]>f[i+1][j+1])
 
                f[i][j]=f[i+1][j]+f[i][j];
 
            else
 
                f[i][j]=f[i+1][j+1]+f[i][j];
 
        }
 
    }
 
    return f[0][0];
 
}
 
int main()
 
{
 
   int n;
 
   cin>>n;
   for(int i=0;i<n;i++)
 
   {
 
       for(int j=0;j<=i;j++)
 
            cin>>f[i][j];
   }
 
   cout<<ff(n)<<endl;
 
}

2、最优解

即输出得到最优值要走的一个路线

求最优解从上往下走：

从f[0][0]出发，sum=f[0][0],row=0,col=0,cout<<row<<col

重复以下过程：

row=row+1;

if(sum-cost[row-1][col]==f[row][col])

{

    sum=f[row][col]

    col不变

}

else

{

    col+=1;   

    sum=f[row][col];

}

cout<<row<<col   

八、点菜（openjudge题目）

题目描述：umi拿到了uoi的镭牌后，立刻拉着基友小A到了一家餐馆，很低端的那种。uim指着墙上的价目表（太低级了没有菜单），说：“随便点”。不过uim由于买了一些书，口袋里只剩M元(M≤10000)。餐馆虽低端，但是菜品种类不少，有N种(N≤100)，第i种卖ai元(ai ≤1000)。由于是很低端的餐馆，所以每种菜只有一份。

小A奉行“不把钱吃光不罢休”，所以他点单一定刚好把uim身上所有钱花完。他想知道有多少种点菜方法。

输入

第一行是两个数字，表示N和M。

第二行起N个正数ai（可以有相同的数字，每个数字均在10001000以内）

#include <iostream>
 
#include<algorithm>
 
using namespace std;
 
/*
 
01背包问题
 
钱 M元
 
菜 N种
 
菜价  a[i]
 
*/
 
const int maxn=10000+10;
 
int a[maxn],f[maxn];
 
int main()
 
{
 
    int n,m;
 
    cin>>n>>m;//共有m元钱
    f[0]=1;//至少有一种点菜方案
 
    for(int i=1;i<=n;++i)
 
        cin>>a[i];
    for(int i=1;i<=n;++i)//每种菜依次进行比较
 
    {
 
 
 
        for(int j=m;j>=a[i];--j)//从现有钱数开始，直至当前菜为止
 
    {
 
        //方案数：当前的花费=之前的花费+不点这个菜的花费
 
        f[j]=f[j]+f[j-a[i]];//j-a[i]点a[i]之后剩余钱数
 
    }
 
    }
 
    cout<<f[m]<<endl;
 
    return 0;
 
}

 

 大家一起加油啊！！！