动态规划

我就是我 2022-12-01 11:51 40阅读 0赞

一：概念：  
和分冶法相似，不同之处在于前者是把问题划分为互不相交的子问题，而动态规划会出现子问题重叠的情况。通常用来求解最优化问题。。  
基本步骤：  
①：刻画一个最优解的结构特征。  
②：递归的定义最优解的值。  
③：计算最优解的值，通常采用自底向上的方法。  
④：利用计算出的信息构造最优解。  
两个基本特征：  
①：最优子结构：最优解由相关子问题的最优解构成。（子问题之间互不相关）  
②：重叠子问题：问题的递归算法会反复求解相同的子问题，而不是一直生成新的子问题。  
二：例子：  
1.钢条切割问题：一根长度为n的钢条，i长度的出售价格为p\[i\]，求解切割之后（可多次切割）的钢条最多卖多少钱。

\*最优解特征：n被切割为j和k，还需要继续分析j和k如何切割。  
\*重叠子问题：在小段为1之前，总是会求解一些相同长度的切割问题。  
\*状态转移方程：q\[n\]=max(p\[i\]+q\[n-i\]);

算法（java）：  
①：自顶向下（分冶法）（不可直接运行)

public class Divide{
        
      int p[]=new int[0,1,5,8,9,10,17,17,20,24,30];//i长度的钢条的价格表（可用哈希表）
      main（）
      {
        
         syso（"请输入要切割的钢条长度n"）；
         Scanner scanner=new Scanner(System.in);
         int n=scanner.nextint();
         scanner.close();   //获取钢条的长度
         int q=0;
         q=Divide(n,q);    //调用自顶向下的算法
         syso(q);     
      }
      public int Divide(int n,int q)
      {
        
        for(int i=0;i<n;i++)
        {
        
          q=Math.max(q,Divide(n-i,q))//状态转移方程
        }
        return q;
      }
     /*因为采用的是自顶向下的算法，会重复计算多个重叠子问题，可以一个数组暂时保存已经求解过的子问题，即动态规划
     */
    }

②自底向上（动态规划）（不可直接运行）：

//不会重复计算子问题。
    public class Divide{
        
      int p[]=new int[0,1,5,8,9,10,17,17,20,24,30];//i长度的钢条的价格表（可用哈希表）
      main（）
      {
        
         syso（"请输入要切割的钢条长度n"）；
         Scanner scanner=new Scanner(System.in);
         int n=scanner.nextint();
         scanner.close();   //获取钢条的长度
         int q[]=new int[n];//分别对应i长度的钢条的最佳切割结果价格
         q[0]=0;
         for(int i=0;i<n;i++)
         {
        
           int q=0;
           for(int j=0;j<i;j++)
           {
        
             q=Math.max(q,q[j]+q[i-j]);//状态转移方程
           }
           q[j]=q;//更新最优解数组
         }
         syso(q[n]);
         return q[n];//返回要求的值
      }

2.最长公共子序列问题：  
求出两个序列中的最长公共子序列，不要求连续，例如：S1=ACCGT，  
S2=ACCT，则输出结果X=ACCT。

\*最优子结构：S1的前n1个字符和S2的前n2个字符的最长公共子序列将是S1和S2的整个最长公共子序列的前缀。S1的前n1个字符或者S2的前n2个字符也可看做是序列，短序列的解是长序列的解，即子问题的解是大问题的解，所以满足最优子结构。  
\*\*重叠子问题：计算比较长的序列的最长公共子序列会多次重复计算较短序列的最长公共子序列  
\*状态转移方程：C\[I,j\]表示S1的0到i个元素和S2的0到j个元素的最长公共子序列。  
C\[I,j\]=  
① 0 (i=0&&j==0)  
② C\[i-1,j-1\]+1 (S1i=S2j)  
③Max\{C\[i-1，j\]，C\[j-1,i\]\} (S1i!=S2j)

算法思想：  
用C\[\]\[\]来维护最长公共子序列的长度  
用b\[\]\[\]来保存序列。  
算法代码（java）（动态规划）（不可直接运行）：

LCS-Length(String S1,String S2)
    {
        
      m=S1.length();
      n=S2.length();
      int C[][]=new int[m][n];//长度数组
      int b[][]=new int[m][n];//前驱序列数组
      for(int i=0;i<m;i++)//初始化第一列
      {
        
         C[i][0]=0;
      }
      for(int i=0;i<n;i++)//初始化第一行
      {
        
        C[0][i]=0;
      }
      for(int i=0;i<m;i++)         //根据状态转移方程循环
      {
        
        for(int i=0;i<n;i++)
        {
        
          if(S1[i]==S2[j])
          {
        
             C[i][j]=C[i-1][j-1]+1;
             b[i][j]=3;                      //3代表前序是左上方的序列
          }
          else
          {
        
            if(C[i-1][j]>=C[i][j-1])
            {
        
               C[i][j]=C[i-1][j];
               b[i][j]=2;                  //代表前驱是上方的序列
            }
            else
            {
        
               C[i][j]=C[i][j-1];
               b[i][j]=1;  
            }
          }
        }
      }
    }
    LCS-print(String S1,String S2,int b[][],int i,int j)//输出最长序列
    {
        
      if(b[i][j]==3)//b[i][j]=3说明S1i是等烟雨S2j的，是最长公共子序列的一个元素，输出即可
      {
        
        syso(S1i);
        LCS-print(S1, S2, b[][], i-1,j-1);
      }
      else if(b[i][j]==2)//等于2的情况对应最长公共子序列是S1（i-1）和S2j的最长公共子序列
      {
        
        LCS-print(S1, S2, b[][], i-1,j);
      }
      else //等于1的情况对应最长公共子序列是S1i和S2（j-1）的最长公共子序列
      {
        
        LCS-print(S1, S2, b[][], i,j-1);
      }
    }