您现在的位置是：首页 >其他 >【算法】动态规划网站首页其他

一、基础知识

动态规划的基本思想：将待求解问题分解成若干个子问题，如果各个子问题不是独立的，不同的子问题的个数只是多项式量级，为避免大量的重复计算，用一个表记录所有已解决的子问题的答案，而在需要的时候再找出已求得的答案。
分治与动态规划算法的异同：
相似之处:

1. 都可以将大问题划分为小问题求解。
2. 都需要重叠子问题的最优解。

不同之处:

1. 分治算法是自上而下,递归求解,然后合并结果。动态规划是自下而上,从更小的子问题开始递推。

2. 分治算法对每个子问题只计算一次,不会重复计算。动态规划算法会存储每个子问题的解,重复使用,避免重复计算。

3. 分治算法不需要存储中间结果,只存储最终结果。动态规划需要创建一个表来存储各个子问题的解。

4. 分治算法对每个子问题的解需要进行合并,而动态规划只需要简单地查表即可得到解。

5. 分治算法的时间复杂度较高,常为O(nlogn)。动态规划能达到O(n)的时间复杂度。

   总之,分治算法采用自上而下的分解方式,只存储最终结果,要进行结果合并,效率较低。动态规划采用自下而上递推的方式,存储每个子问题的最优解,通过查表得到最终解,效率较高。

理解动态规划算法的基本要素：

1. 最优子结构性质：问题的最优解包含了其子问题的最优解。
2. 重叠子问题性质：有些子问题被反复计算多次。

动态规划算法求解问题的步骤：

1. 找出最优解的性质，并刻画其结构特征
2. 递归地定义最优值
3. 以自底向上的方式计算出最优值
4. 构造最优解

二、矩阵连乘问题

伪代码：

//用动态规划法求解
void MatrixChain(int *p，int n，int **m，int **s)
{
        for (int i = 1; i <= n; i++) m[i][i] = 0;//矩阵链长度为1
        for (int r = 2; r <= n; r++)   //r为矩阵链长度，从2…n
           for (int i = 1; i <= n - r+1; i++) 
          {//遍历所有长度是r的子问题。
           //对于每一个给定的链长r，左边界为i，右边界为j
              int j=i+r-1;
              m[i][j] = +∞; 
              s[i][j] = i;//记录断开位置，即加括号的位置
              for (int k = i; k < j; k++)
              {//矩阵链的分隔位置从第i个矩阵…第j-1个矩阵
                 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;}
              }
          }
}

三、最长公共子序列问题

int  LCSLength(char *x,char *y,int  c[ ][N],int  b[ ][N])
{     
     //x和y的长度     
     int m=strlen(x),n=strlen(y);  
     int i,j;  
     //初始化c[][]  
     for (i = 0; i <= m; i++) c[i][0] = 0;  
     for (i = 0; i <= n; i++) c[0][i] = 0;  
     //计算c[][]
     for (i = 1; i <= m; i++)   
        for (j = 1; j <= n; j++)
     {
           //如果两个字符相同,左上方的值加1   
           if (x[i-1]==y[j-1]) {    
                c[i][j]=c[i-1][j-1]+1; b[i][j]=1;    
           }   
           //如果不相同,取左方和上方的最大值  
           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]=3; }  
     }  
     //返回最长公共子序列长度
     return  c[m][n];
}
//通过b[][]回溯构造最长公共子序列 
void LCS(int i,int j,char *x,int **b)  
{   
     //到达边界,返回  
     if (i ==0 || j==0) return;     
     //向左上方移动 
     if (b[i][j]== 1){ LCS(i-1,j-1,x,b); cout<<x[i]; }     
     //向左方移动
     else if (b[i][j]== 2) LCS(i-1,j,x,b);   
     //向上方移动
     else LCS(i,j-1,x,b);  
}

四、最大子段和问题

int maxSum(int a[],int n,int &begin,int &end){
    int sum=0;   //结果,最大子序列和
    int b=0;     //当前和
    for(int i=0;i<n;i++){
        if(b>0) b+=a[i]; //如果b大于0,加上当前元素 
        else{  
            b=a[i];   //如果b等于0,重新开始,b赋值为当前元素值
            begin=i;  //记录开始位置  
        }
        if(b>sum){ //如果当前和大于结果,更新结果和结尾位置 
            sum=b;   
            end=i;  
        }   
    }
    return sum;   //返回结果
} 

五、0-1背包问题

int  Knapsack(int v[], int w[], int c, int n, m[][])  
{     
    //初始化第一行和第一列,均为0
    for(int i=0;i<=n;i++)  m[i][0]=0;  
    for(int j=0;j<=c;j++)  m[0][j]=0;  
    //自底向上计算每个子问题的最优值
    for(i=1;i<=n;i++) 
    for(j=1;j<=c;j++)
   {     
        //如果不能装下,最大价值就是不考虑该物品的价值
        if(j<w[i]) 
          m[i][j]=m[i-1][j];     
        //如果能装下,取决于装入或不装入该物品的最大值
        else
          m[i][j]=max(m[i-1][j], m[i-1][j-w[i]]+v[i]);
   }  
   //返回总的最大价值
   return m[n][c];
}