大家好，欢迎来到IT知识分享网。

动态规划

动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适用于动态规划法求解的问题，经分解得到的子问题往往不是相互独立的。在用分治法求解的时候，有些子问题被重复计算了许多次。如果能够保存已解决的子问题的答案，而在需要的时候再找出已求得的答案，就可以避免大量重复计算，从而得到多项式时间的算法。

动态规划算法适用于解最优化问题，通常可以按以下步骤设计的动态规划算法：

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

最大子段和

先来看一下最大子段和用分治法思想的分析：

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

1. a[1 : n]的最大子段和同a[1 : n/2]的最大子段和相同。
2. a[1 : n]的最大子段和同a[n/2 : n]的最大子段和相同。
3. a[1 : n]的最大子段和等于位于a[1 : n/2]的子段和和位于a[n/2+1 : n]的子段和的和

1和2的情况可以直接递归求得，第3种情况，a[n/2]和a[n/2+1]在最优子序列之中，我们只需要计算出左边a[1 : n/2]从n/2开始的最大子段和s1，右边a[ n/2+1 : n]从n/2+1开始的最大子段和，然后将两者相加s=s1+s2；s即为第3种情况的最优值。

算法思想

从上述分治法思想注意到，我们可以记b[ j ]为1 ~ j 中的最大子段和，其中j∈[1，n]；

这样，那么所求的1 ~ n 中的最大子段和就为 i~j 的和可以表示为：

意思就是，j从1到n，依次找到最大子段和。

由b[ j ]的定义易知，当b[ j-1 ]>0 时b[ j ]= b[ j-1 ] +a[j]，否则 b[ j ]=a[ j ]。 由此可得计算b[j]的动态规划递归式：

b[j] = max {b[j-1] +a[j], a[j] } ，1≤j ≤ n

当前的最优解，就等于前一个最优解加上当前值和当前值中的较大者。

伪代码

public static int MaxSum(int []a,int n)
{
	int sum=0;
	int b=0;
	for(int i=0;i<n;i++)
	{
		if(b>0)
            b+=a[i];
        else 
            b=a[i];
        if(b>sum)
            sum=b;
	}
    return sum;
}

矩阵连乘问题

给定n个矩阵{A1，A2……An} ， 其中Ai与Ai+1可乘，i=1,2,3…n-1 。 如何确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。

考察这n个矩阵的连乘积 A1A2…An

由于矩阵乘法满足结合律，所以计算矩阵的连乘可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。

若一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已完全加括号，则可以依此次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积。

基本思想

将矩阵连乘积 AiAi+1…Aj简记为A[i:j] ，这里i ≤ j 考察计算A[i:j]的最优计算次序。设这个计算次序在矩阵 Ak和Ak+1之间将矩阵链断开，i≤k<j，则其相应完全加括号方式为

计算量：A[i:k]的计算量加上A[k+1:j]的计算量，再加上 A[i:k]和A[k+1:j]相乘的计算量。

最优解结构：

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

• 矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法求解的显著特征。

建立递归关系：

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

2. 当i=j时，A[i:j]=Ai，因此，m[i,i]=0，i=1,2,…,n

3. 当i<j时，m[i , j]=m[i , k] + m[k+1 , j] + pi-1 * pk * pj ，这里Ai的维数为pi-1 * pi

4. 递归的定义m[i , j]为：

   

   k的位置只有j-i种可能。

计算的时候是斜着对角进行计算的，这样再计算下一轮的时候就可以用到前面已经求得的值。

计算过程：

比如m[2] [5]就可以表示为：

伪代码

public void matrixChain(int []p,int n,int [][]m,int [][]s)
{
    //初始化对角线全为0 因为当i=j时，A[i:j]=Ai，因此，m[i,i]=0
    for(int i=1;i<=n;i++) m[i][i]=0;
    for(int r=2;r<=n;r++)
        for(int i=1;i<=n-r+1;i++)
        {
            int j=i+r-1;
            //这是把 m[i][j]分成i->i i+1->j的情形，m[i][i]=0
            //m[i , j]=m[i , k] + m[k+1 , j] + pi-1 * pk * pj
            m[i][j]= m[i+1][j]+ p[i-1]*p[i]*p[j];
            s[i][j] = i;
            //这里就是除了i->i i+1->j的情形以外的情况，要找到最小值
            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;
                }
            }
        }
}

算法复杂度分析： 算法matrixChain的主要计算量取决于算法中对r，i 和 k 的3重循环。循环体内的计算量为O(1)，而3重循环的总次数为O(n^3 )。因此算法的计算时间上界为O(n^3 )。算法所占用的空间显然为O(n^2 )。

最长公共子序列问题

若给定序列X={x1 ,x2 ,…,xm}，则另一序列 Z={z1 ,z2 ,…,zk }，是X的子序列是指存在一个严格递增 下标序列{i1 ,i2 ,…,ik }使得对于所有j=1,2,…,k有：zj=xi。 例如，序列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的最长公共子序列。

基本思想

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

• 若xm==yn，则zk=xm=yn。X与Y的最长公共子序列为{x1 ,x2 ,…,x(m-1)}，{y1 ,y2 ,…,y(n-1) }的最长公共子序列+xm
• 若xm!=yn且zk!=xm，则X与Y的最长公共子序列为{x1 ,x2 ,…,x(m-1)}，{y1 ,y2 ,…,yn }的最长公共子序列
• 若xm!=yn且zk!=yn，则X与Y的最长公共子序列为{x1 ,x2 ,…,xm}，{y1 ,y2 ,…,y(n-1) }的最长公共子序列

由此可见，2个序列的最长公共子序列包含了这2个序列的前缀 的最长公共子序列。因此，最长公共子序列问题具有最优子结 构性质。

由最长公共子序列问题的最优子结构性质建立子问题最优值的递归关系。用c[i] [j]记录序列和的最长公共子序列的长度。其中，Xi={x1 ,x2 ,…,xi }；Yj={y1 ,y2 ,…,yj }。当i=0或j=0时，空序列是Xi和Yj的最长公共子序列。故此时C[i] [j]=0。其它情况下，由最优子结构性质可建立递归关系如下：

Algorithms和alchemist：

i=0和j=0，则c[i] [j]为0；然后，首先X1 A 和Y1 A相同，那么就取左上方c[i-1] [j-1]+1 ；接下来，X1 A和Y2 L不同，则c[i] [j] 就等于左边c[i] [j-1] 和 上边 c[i-1] [j] 中的较大者。

伪代码

public void LCSLength(int m,int n,char []x,char []y,int [][]c,int [][]b)
{
    int i=1;
    int j=1;
    //i=0或者j=0，空序列为最长公共子序列，因此c[i][j]=0
    for(i=1;i<=m;i++)
        c[i][0]=0;
    for(i=1;i<=n;i++)
        c[0][i]=0;
    
    for (i = 1; i <= m; i++)
		for (j = 1; j <= n; j++) 
        {
			if (x[i]==y[j]) 
            { 
				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;
            }
        }
}

//构造最长公共子序列
public 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); 
        System.Out.print(x[i]+" ");
    }
	else if (b[i][j]== 2) 
        LCS(i-1，j，x，b);
	else LCS(i，j-1，x，b);
}

算法LCSLength耗时O(m*n)，算法LCS的计算时间为O(m+n)。

0-1背包问题

给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为C。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大?

设所给0-1背包问题的子问题

的最优值为m[i] [j]，即m(i,j)是背包容量为j，可选择物品为i，i+1，…，n时0-1背包问题的最优值。

由0-1背包问题的最优子结构性质，可以建立如下计算m(i，j)的递归式：

递归式的意思就是：如果当前背包容量小于当前物品的重量，那么就是不能装下，这样就等于下一个到m(i+1 , j)。如果当前背包容量能大于当前物品的重量，那么就是能装下，这样就只需要比较装下该物品（如果选择装下该物品，那么前面物品的总价值就会被压缩，因为该物品占了重量所以要去找m(i+1 , j-wi)然后再加上刚装下物品的价值）或者不装该物品，哪一个得到的价值更大。

伪代码

public void knapsack(int []v,int []w,int c,int [][]m)
{
    int n=v.length-1;
    for(int i=0;i<c;i++)
        m[0][i]=0;
    for(int i=0;i<n;i++)
        m[i][0]=0
    for(int i=1;i<n;i++)
        for(int j=1;j>=c;j++)
        {
            if(j>=w[i])
                m[i][j]=max(m[i-1][j],m[i-1][j-w[i]]+v[i]);
            else
                m[i][j]=m[i-1][j];
        }
}

这里用m[i][j]=max(m[i-1] [j],m[i-1] [j-w[i]]+v[i]);同上方i+1意思是一样的，只不过初始化不同。

时间复杂度O(nc)；