美文网首页动态规划
动态规划经典问题

动态规划经典问题

作者: 鱼游硅谷 | 来源:发表于2015-01-05 08:58 被阅读3154次

    1. 塔树选择和最大问题

    (见塔树选择和最大问题)

    一个高度为N的由正整数组成的三角形,从上走到下,求经过的数字和的最大值。每次只能走到下一层相邻的数上,例如从第3层的6向下走,只能走到第4层的2或9上。

       5
      8 4
     3 6 9
    7 2 9 5
    

    例子中的最优方案是:5 + 8 + 6 + 9 = 28。

    • 分析
      直接分析,从上到下的考虑,发现无从下手好像只能遍历,但是反方向考虑则,则发现有趣的地方,假设dp[i][j]为最下面一层到第i层j位置上的最大值,考虑上图6这个位置,那么其dp[3][2]应该是什么呢?是下面相邻的两个位置的最大值+6,即dp[3][2] = max(dp[3+1][2],dp[3+1][2+1]) + a[3][2]。
      据此可以推导其公式为
      dp[i][j] = max(dp[i+1][j],dp[i+1][j+1]) + a[i][j]
      根据上述公式编程思路如下
      1、初始化最下面一排dp
      2、由下往上,安装上述公式对dp进行赋值
      3、dp[1][1]为最终所求
     //最下面一层直接赋值
      int rs = 0;    
      for (int i = 0; i<FLOOR; i++)
            dp[FLOOR-1][i] = a[FLOOR-1][i];
      //从倒数第二行起, 按照状态转移方程
      //dp[i][j] = max(dp[i + 1][j], dp[i + 1][j + 1]) + a[i][j]向上递推
      //直到dp[0][0], 此时dp[0][0]就是结果
      for (int i = FLOOR-2; i>=0; i--)
          for (int j = 0; j<=i;j++)
              dp[i][j] = max(dp[i+1][j],dp[i+1][j+1])+a[i][j];
    

    启示:动态规划解决问题时,经常从后面往前考虑会瞬间明朗很多,塔数类问题还有许多其他的变形参见 动态规划“数塔”类型题目总结

    2. 乘法表问题

    定义于字母表∑(a,b,c)上的乘法表如表1所示

    • 表1. ∑乘法表

    ∑ | a |b | c
    :---:|:---:|:---:|:---:
    a |b | b | a
    b |c | b| a
    c |a | c | c
    依此乘法表,对任一定义于∑上的字符串,适当加括号表达式后得到一个表达式。例如,对于字符串x=bbbba,它的一个加括号表达式为i(b(bb))(ba)。依乘法表,该表达式的值为a。试设计一个动态规划算法,对任一定义于∑上的字符串x=x1x2…xn,计算有多少种不同的加括号方式,使由x导出的加括号表达式的值为a
    要求:
    输入:输入一个以a,b,c组成的任意一个字符串。
    输出:计算出的加括号方式数。

    • 分析:
      建立一个三位数组,用于记录一段连续的序列内通过加括号可得到a、b、c的方式数,然后往长度方向扩展,因为每两个字母相乘的结果已给出,所以可通过加和乘运算求出更大长度的字符串得到a、b、c的方式数

    • 具体算法:
      数组维数为:p[n][n][3];
      p[i][j][k] 表示 字符串xix(i+1)....xj的表达式的值为k(k>=0 k <=2,k=0表示a...) 的方式数;
      递推式为:
      p[i][j][0]= sum(p[i][t][0]*p[t+1][j][2]+ p[i][t][1]*p[t+1][j][2]+p[i][t][2]*p[t+1][j][0])
      p[i][j][1]与p[i][j][2]类似p[i][j][0] 的求法 t>=i 并且t <j

    C++代码:

    #include <stdio.h>   
    #include <string.h>   
    int main() {   
        int n = 0;   
        char c;   
        int p[100][100][3] = {0};   
        while((c = getchar()) != '/n') {   
            p[n][n][c - 'a'] = 1;   
            n++;   
        }      
        for(int k = 1;k < n;k++) {   
            for(int i = 0;i < n-k;i++) {   
                int j = i + k;   
                for(int t = i;t < j;t++) {   
                    p[i][j][0] += p[i][t][2]* p[t+1][j][0] + p[i][t][0]*p[t+1][j][2] + p[i][t][1]*p[t+1][j][2];   
                    p[i][j][1] += p[i][t][0]*p[t+1][j][0] + p[i][t][0]*p[t+1][j][1] + p[i][t][1]*p[t+1][j][1];   
                    p[i][j][2] += p[i][t][1]*p[t+1][j][0] + p[i][t][2]*p[t+1][j][1] + p[i][t][2]*p[t+1][j][2];   
                }   
            }   
        }   
        printf("%d/n",p[0][n-1][0]);   
    }  
    

    3. 爬楼梯

    题目:
    You are climbing a stair case. It takes n steps to reach to the top.
    Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

    • 分析:
      动态规划 d(i) = d(i-1) + d(i-2)
    class Solution:
        # @param n, an integer
        # @return an integer
        def climbStairs(self, n):
            dp = [0, 1, 2]
            if n <= 2:
                return dp[n]
            dp += [0 for i in range (n-2)]
            for i in range (3, n + 1):
                dp[i] += dp[i-1] + dp[i-2]
    
            return dp[n]
    

    4. 最长上升子序列(LIS)

    问题描述:
    设L=<a1,a2,…,an>是n个不同的实数的序列,L的递增子序列是这样一个子序列Lin=<aK1,ak2,…,akm>,其中k1<k2<…<km且aK1<ak2<…<akm。求最大的m值。

    • 分析:
      这里采用的是逆向思维的方法,从最后一个开始想起,即先从A[N](A数组是存放数据的数组,下同)开始,则只有长度为1的子序列,到A[N-1]时就有两种情况,如果a[n-1] < a[n] 则存在长度为2的不下降子序列 a[n-1],a[n];如果a[n-1] > a[n] 则存在长度为1的不下降子序列 a[n-1]或者a[n]。
      有了以上的思想,DP方程就呼之欲出了(这里是顺序推的,不是逆序的):
    DP[I]=MAX(1,DP[J]+1)  J=0,1,...,I-1
    

    但这样的想法实现起来是)O(n^2)的。本题还有更好的解法,就是O(n*logn)。利用了长升子序列的性质来优化,以下是优化版的代码:

    //最长不降子序       
    const int SIZE=500001;
    int data[SIZE];
    int dp[SIZE];
     
    //返回值是最长不降子序列的最大长度,复杂度O(N*logN)
    int LCS(int n) {            //N是DATA数组的长度,下标从1开始
        int len(1),low,high,mid,i;
     
        dp[1]=data[1];    
        for(i=1;i<=n;++i) {
           low=1;
           high=len;
    
           while( low<=high ) {   //二分
               mid=(low+high)/2;
               if( data[i]>dp[mid] ) {
                    low=mid+1;
               }
               else {
                    high=mid-1;
               }
           }
     
           dp[low]=data[i];
           if( low>len ) {
                ++len;
           }
        }
        return len;
    }
    

    5. 背包问题

    有N件物品和一个容量为V的背包。第i件物品的大小是c[i],价值是w[i]。求解将哪些物品装入背包可使价值总和最大。

    分析:

    用DP[I][J] 表示前I件物品放入一个容量为J的背包可以获得的最大价值。则

      DP[I][J]=     DP[I-1][J]  ,J<C[I]
                    MAX(DP[I-1][J],DP[I-1][J-C[I]]+W[I])  , J>=C[I]
    

    这样实现的空间复杂度为O(VN),实际上可以优化到O(V)。以下是代码:

    const int MAXW=13000;    //最大重量
    const int MAXN=3450;     //最大物品数量
     
    int c[MAXN];     //物品的存放要从下标1开始
    int w[MAXN];     //物品的存放要从下标1开始
    int dp[MAXW];
     
    //不需要将背包装满,则将DP数组全部初始化为0
    //要将背包装满,则初始化为DP[0]=0,DP[1]…DP[V]=-1(即非法状态)
    int Packet(int n,int v) {
          int i,j;
          memset(dp,0,sizeof(dp));
          for(i=1;i<=n;++i) {
              for(j=v;j>=c[i];--j) {  //这里是倒序,别弄错了
                  dp[j]=MAX(dp[j],dp[j-c[i]]+w[i]);
              }
          }
     
          return dp[v];
    }
    

    6. 最长公共子序列(LCS)

    给出两个字符串a, b,求它们的最长、连续的公共字串。

    这很容易就想到以DP[I][J]表示A串匹配到I,B串匹配到J时的最大长度。则:

    0                              I==0 || J==0
    DP[I][J]= DP[I-1][J-1]+ 1                  A[I]==B[J]
              MAX(DP[I-1][J],DP[I][J-1])   不是以上情况
    

    但这样实现起来的空间复杂度为O(n^2),而上面的方程只与第I-1行有关,所以可以用两个一维数组来代替。以下是代码:

          //最长公共子序列
    const int SIZE=1001;
    int dp[2][SIZE];   //两个一维数组
     
    //输入两个字符串,返回最大的长度
    int LCS(const string& a,const string& b) {
         int i,j,flag;
         memset(dp,0,sizeof(dp));
     
         flag=1;
         for(i=1;i<=a.size();++i) {
             for(j=1;j<=b.size();++j) {
                 if( a[i-1]==b[j-1] )      dp[flag][j]=dp[1-flag][j-1]+1;
                 else                  dp[flag][j]=MAX(dp[flag][j-1],dp[1-flag][j]);       
             }
             flag=1-flag;
         }
     
         return dp[1-flag][b.size()];
    }
    

    另见 LCS

    相关文章

      网友评论

        本文标题:动态规划经典问题

        本文链接:https://www.haomeiwen.com/subject/ncktxttx.html