动态规划总结

深碍√TFBOYSˉ_ 2022-08-11 07:30 200阅读 0赞

本文转载自：[风中之炎 不盛则灭][Link 1]

本文着重讨论状态是如何表示，以及方程是怎样表示的。当然，还附上关键的，有可能作为模板的代码段。但有的代码的实现是优化版的，这里就不解释了。因为不是本文的重心。

***经典问题总结***

**最长上升子序列（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;
    }

**最长公共子序列（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()];
    }

//博主感觉这样会更简洁

int dp[2][N];
    
    
    int LCS(string a,string b) 
    {
    	memset(dp,0,sizeof(dp));
    	int i,j;
    	for(i=1;i<=a.size();i++)
    	{
    		for(j=1;j<=b.size();j++)
    		{
    			if(a[i-1]==b[j-1])dp[i%2][j]=dp[(i-1)%2][j-1]+1;
    			else dp[i%2][j]=max(dp[i%2][j-1],dp[(i-1)%2][j]);
    		}
    	}
    	return dp[a.size()%2][b.size()];
    }

**01背包**

有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];
    }

**完全背包问题**

有N种物品和一个容量为V的背包，每种物品都有无限件可用。第i种物品的费用是c\[i\]，价值是w\[i\]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

很容易可以得到这种状态表示：用DP\[I\]\[J\] 表示前I件物品放入一个容量为J的背包可以获得的最大价值。则

DP[I][J]=MAX（DP[I-1][J]，DP[I-1][J-K*C[I]]+K*W[I]） 0<=K*C[I]<=J

这样的复杂度是O(V\*Σ(V/c\[i\]))

有更好的做法，那就是利用01背包的优化原理。在优化的代码中，之所以第二重循环是倒序，是为了防止重复拿，那么只要将其变为顺序即可以重复取。代码就不给了。

**多重背包问题**

有N种物品和一个容量为V的背包。第i种物品最多有n\[i\]件可用，每件费用是c\[i\]，价值是w\[i\]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

这题仍然可以用到上一题的思想，DP表示状态与上面的相同。方程为：

DP\[I\]\[J\]=MAX（DP\[I-1\]\[J\]，DP\[I-1\]\[J-K\*C\[I\]\]+K\*W\[I\]）

不同的是K的范围，0<=K<=N\[I\] && 0<=K\*C\[I\]<=J

这样的复杂度为O(V\*Σn\[i\])。

有更好的想法就是先用二进制来划分。将第i种物品分成若干件物品，其中每件物品有一个系数，这件物品的费用和价值均是原来的费用和价值乘以这个系数。使这些系数分别为1,2,4,...,2^(k-1),n\[i\]-2^k+1，且k是满足n\[i\]-2^k+1>0的最大整数。然后用01背包做，这样的复杂度为O(V\*Σlog n\[i\])。关键代码：

<pre name="code" class="cpp">const int SIZE=1001;
    int dp[SIZE];
    int num[SIZE],c[SIZE],w[SIZE];  //num[i]是I物品的件数,C[I]是费用，W[I]是价值
    int MultiPack(int n,int v)    //存入参数，N是物品种类数，V是背包容量
    {
        int i,j,k;
        memset(dp,0,sizeof(dp));
        for (i=1;i<=n;++i)  //存放物品的数组下标从1开始
        {
            if ( c[i]*num[i]>=v )
            {
                for (j=c[i];j<=v;++j)
                {
                    dp[j]=MAX(dp[j],dp[j-c[i]]+w[i]);
                }
            }
            else    //使用二进制划分
            {
                k=1;
                while ( k<num[i] )
                {
                    for (j=v;j>=k*c[i];--j)
                    {
                        dp[j]=MAX(dp[j],dp[j-k*c[i]]+k*w[i]);
                    }
                    num[i]-=k;
                    k*=2;
                }
                for (j=v;j>=num[i]*c[i];--j)
                {
                    dp[j]=MAX(dp[j],dp[j-num[i]*c[i]]+num[i]*w[i]);
                }
            }
        }
        return dp[v];
    }

[Link 1]: http://blog.sina.com.cn/qkhhdnfss