记录结果再利用的动态规划——《挑战程序设计竞赛》

2.3.1 记忆化搜索与动态规划

01 背包问题
有n个重量和价值分别为$w_i, v_i$的物品。从这些物品中挑选出总重量不超过W的物品，求所有挑选方案中价值总和的最大值。

循序渐进，先用最朴素的递归方法，针对每个物品是否放入背包进行搜索试试看。

int n, W;
const int MAX_N = 10010;
int w[MAX_N], v[MAX_N];

//从index为i的物品开始挑选总重小于j的部分
int rec(int i,int j)
{
	int res;
	if(i==n) //没有剩余的物品了
	{
		res = 0;
	}
	else if(w[i]>j)//index为i的物品重量大于剩余总重
	{
		res = rec(i+1,j);
	}
	else
	{
		res = max(rec(i+1,j),rec(i+1,j-w[i]) + v[i]);
	}
	return res;
}

void solve()
{
    printf("%d\n", rec(0,W));
}

这种方法搜索深度为n，如第19行所示，每一层都有两个分支，那么最坏的复杂度为$O(2^n)$。因为会有相同参数的rec的多次调用，重复计算，耗时费神。故记忆化搜索的想法是把第一次计算的结果记录下来，之后直接调用以防重复计算。

int dp[MAX_N+1][MAX_N+1];
int rec(int i,int j)
{
	if(dp[i][j]>=0)
	{
		return dp[i][j];
	}
	int res;
	if(i==n) //没有剩余的物品了
	{
		res = 0;
	}
	else if(w[i]>j)//index为i的物品重量大于剩余总重
	{
		res = rec(i+1,j);
	}
	else
	{
		res = max(rec(i+1,j),rec(i+1,j-w[i]) + v[i]);
	}
	dp[i][j] = res;
	return res;
}

void solve()
{
	memset(dp,-1,sizeof(dp));//-1表示尚未被计算过，初始化整个数组
    printf("%d\n", rec(0,W));
}

代码中直观地实现了我们记录第一次计算结果的想法，这就是记忆化搜索，也就是dp的萌芽。rec函数参数的组合最大nW种，所以时间复杂度为O(nW)。

memset进行初始化是按照1字节为单位对内存进行填充的，因为-1的二进制表示每一个比特位都是1，所以可以用memset初始化为-1，0也可以用memset初始化，但是不能初始化从1之类的数值，因为1的二进制表示为00000001，memset不能细粒度到每个比特。

但这并不是正经的DP格式，DP需给出递推关系，如下：

定义dp[i+1][j]:=从0到i这i+1个物品中选出总重量不超过j的物品时总价值的最大值,则有

$$\begin{equation} dp[0][j]=0 \\ dp[i+1][j] = \left\{ \begin{array}{**lr**} dp[i][j], & (j<w[i]) \\ max(dp[i][j],dp[i][j-w[i]]+v[i]) & (其他) \end{array} \right. \end{equation}$$

基此，因为dp为两维数值，两层循环的代码如下：

int solve()
{
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<=W;j++)
		{
			if(j<w[i]) dp[i+1][j] = dp[i][j];
			else dp[i+1][j] = max(dp[i][j],dp[i][j-w[i]]+v[i]);
		}
	}
	return dp[n][W];
}

2.3.2 进一步探索递推关系

完全背包问题
有n个重量和价值分别为$w_i, v_i$的物品。从这些物品中挑选出总重量不超过W的物品，求所有挑选方案中价值总和的最大值，在这里，每种物品可以挑选任意多件

给出递推关系，很容易得到：
dp[0][j] = 0
dp[i+1][j] = max{dp[i][j-k$\times$w[i]]+k$\times$v[i] | 0 $\le$ k}
这个递推关系中出现了一个新变量k，故如果按照这个递推关系来写代码的话，在dp二维数组的两层循环下还需加一层k的循环，k$\times$w[i] $\le$ j。三层循环的复杂度为$O(NW^2)$。

然而，在dp[i+1][j]的计算中选择k(k$\ge$1)个的情况，与在dp[i+1][j-w[i]]的计算中选择k-1个的情况是相同的，所以dp[i+1][j]的递推中k$\ge$1部分的计算已经在dp[i+1][j-w[i]]的计算中完成了。那么可按照如下方式进行变形

$$\begin{align} & \max\{ dp[i][j-k\times w[i]+k\times v[i]|0 \le k]\}\\ & =\max(\{ dp[i][j],\max\{dp[i][j-k\times w[i]]+k\times v[i]|1 \le k\})\\ & =\max(\{ dp[i][j],\max\{dp[i][(j-w[i])-k\times w[i]]+v[i]+k\times v[i]|0 \le k\})\\ & = \max(dp[i][j], dp[i+1][j-w[i]]+v[i]) \\ \end{align}$$

基此，完全背包问题的代码如下，时间复杂度为$O(bW)$，这给我的区分是，递推关系中多出一个未知数的求最值或者是求和的，大都可变换形式消除未知数，从而降维，减少时间复杂度：

int solve() 
{
	for(int i=0;i<n;i++)
    {
        for(int j=0;j<=W;j++)
        {
            if(j<w[i]) dp[i+1][j] = dp[i][j];
            else dp[i+1][j] = max(dp[i][j],dp[i+1][j-w[i]]+v[i]);
        }
    }
    return dp[n][W];
}

01背包问题和完全背包问题都可以重复利用数组来节省内存空间，因为01背包问题的dp[i+1]计算时只需要dp[i]，可以改进代码如下：
01背包问题

int dp[MAX_W+1];
int solve() 
{
	for(int i=0;i<n;i++)
    {
        for(int j=W;j>=w[i];j--)
        {
        	dp[j] = max(dp[j],dp[j-w[i]]+v[i]);
        }
    }
    return dp[n][W];
}

完全背包问题

int dp[MAX_W+1];
int solve() 
{
	for(int i=0;i<n;i++)
    {
        for(int j=w[i];j<=W;j++)
        {
        	dp[j] = max(dp[j],dp[j-w[i]]+v[i]);
        }
    }
    return dp[n][W];
}

两者的差异只有第二层循环的方向，这样写极易留下bug，需要格外小心。

01背包问题，换限制，若W很大，如 $1\le W \le 10^9$，这样原先的$O(nW)$便不能通过测试，而相较重量而言，此时价值的范围比较小，所以可以试着改变DP的对象，之前的方法中对于不同的重量限制计算最大的价值，这次不妨针对不同的价值计算最小的重量。

定义dp[i+1][j]:=从0到i这i+1个物品中选出价值总和为j时的物品总重量的最小值,则有

dp[0][0] = 0
dp[0][j] = INF

便可顺理成章地得到递推关系式：

$$dp[i+1][j] = \min(dp[i][j],dp[i][j-v[i]]+w[i])$$

利用这一推式可得最终的答案就是令$dp[n][j] \le W$的最大的j。此时，这种DP方式的复杂度即为$O(b\sum_i v_i)$。

此类的改变DP对象，改变DP递推关系式的方法在DP问题中十分常见。再如

多重部分和问题：

有n种不同大小的数字$a_i$，每种各$m_i$个，判断是否可以从这些数字之中选出若干使它们的和恰好为K。

朴素的想法是定义 dp[i+1][j]:=用从0到i这i+1种数能否能加和成j。递推关系如下：

$$dp[i+1][j] = (0\le k\le m_i,且k\times a_i \le j时，存在使dp[i][j-k\times a_i]为真的k)$$

代码为：

//输入
int n, k, a[MAX_N], m[MAX_N];
bool dp[MAX_N+1][MAX_K+1];

bool solve()
{
	dp[0][0] = true;
	for(int i=0;i<n;i++)
		for(int j=0;j<=K;j++)
			for(int k=0;k<=m[i]&&k*a[i]<=j;k++)
				dp[i+1]][j] |= dp[i][j-k*a[i]]
	return dp[n][K];	
}

这个算法的复杂度是$O(K\sum_i m_i)$，这样不够好。一般用DP求取bool结果的话会有很大的浪费，相反如果我们在此问题中用dp数组存储$a_i$这个数还剩下多少：
dp[i+1][j]:=用从0到i这i+1种数加和得到j时，i种数最多能剩余多少个( 不能加得j时为-1)

$$\begin{equation} dp[i+1][j] = \left\{ \begin{array}{**lr**} m_i, & (dp[i][j]\ge 0) \\ -1, & (j< a_i 或者 dp[i+1][j-a_i] \le 0) \\ dp[i+1][j-a_i]-1 & (其他) \end{array} \right. \end{equation}$$

这样，只要看最终是否满足$dp[n][K] \ge 0$就知道答案了。这个递推式可以在O(nK)时间内计算出结果，再利用数组重复利用，可以得到以下代码：

int dp[MAX_K+1];
bool solve()
{
	memset(dp,-1,sizeof(dp));
	dp[0] = 0;
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<K;j++)
		{
			if(dp[j]>=0) dp[j]=m[i];
			else if(j<a[i]|| dp[j-a[i]] <= 0) dp[j] = -1;
			else dp[j] = dp[j-a[i]] - 1;
		}
	}
	return dp[K]>= 0;
}

单纯部分和问题（也许是叫这个名字）

有n个正整数，找出其中和为t(t也是正整数)的可能的组合方式。如：
n=5,5个数分别为1,2,3,4,5，t=5；
那么可能的组合有5=1+4和5=2+3和5=5三种组合方式。
输入的第一行是两个正整数n和t，用空格隔开，其中1<=n<=20,表示正整数的个数，t为要求的和(1<=t<=1000)
接下来的一行是n个正整数，用空格隔开。
输出和为t的不同的组合方式的数目。
样例输入
5 5
1 2 3 4 5
样例输出
3

#pragma once
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;

int a[101], n, m, sum, b[101];
void dfs(int k, int idx)
{
	if (k > m) return;
	if (k == m)
	{
		sum++;
		return;
	}
	for (int i = idx + 1; i <= n; i++)
		if (b[i] == 0)
		{
			b[i] = 1;
			dfs(k + a[i], i);
			b[i] = 0;
		}
}
void solved_with_dfs()
{
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++)
		scanf("%d", &a[i]);
	dfs(0, 0);
	printf("%d\n", sum);
}

int dp[1010];
void solved_with_dp()
{
	scanf("%d%d", &n, &m);
	dp[0] = 1;
	for (int i = 1; i <= n; i++)
	{
		scanf("%d", &a[i]);
		for (int j = m; j >= a[i]; j--)
			dp[j] += dp[j - a[i]];
	}
	printf("%d\n", dp[m]);
}

用dfs来解决的方法本质上就是搜索了，司空见惯了。说一下dp的做法。在dp的做法种，数组dp[i]表示组合成和为i的方式数量。那么就有代码中的转移方程：

$$dp[j] += dp[j - a[i]];$$

注意对于j的遍历必须是从m递减到a[i]，因为每一个输入的数a[i]只能在组合和时，只能使用一次。

---

多重背包问题

有n种物品，它们的重量和价值分别是$w_i$和$v_i$。现在要从中选出一些物品使得总重量不超过W，并且价值的和最大。第i种物品最多取$m_i$个。

对于01背包和完全背包问题，我们都能在$O(nW)$的时间内求解，如果用同样的方法求解本题，则状态转移方程为：
  $dp[i][j]:=到第i个物品为止总重量不超过j的所有选法中最大可能的价值$
  $dp[i+1][j]:=\max \{ dp[i][j-k\times w[i]]+k\times v[i] | 0 \le k \le m_i 且 j-k\times w[i] \ge 0\}$
如果使用这个转移方程，复杂度就是O(nmW)，无法在规定时间内求出解。

先看一个例子：取m[i] = 2, v[i] = v, w[i] = w, W > 9 * v，
并假设 f(j) = dp[i - 1][j]，观察状态转移方程右边要求最大值的几项：

  j = 6$\times$ w: f(6$\times$w)、f(5$\times$w)+v、f(4$\times$w)+2$\times$v 这三个中的最大值
  j = 5$\times$w: f(5$\times$w)、f(4$\times$w)+v、f(3$\times$w)+2$\times$v 这三个中的最大值
  j = 4$\times$w: f(4$\times$w)、f(3$\times$w)+v、f(2$\times$w)+2$\times$v 这三个中的最大值

显然，状态转移方程右边求最大值的几项随j值改变而改变。但如果将j = 6$\times$w时，每项减去6$\times$v，j=5$\times$w时，每项减去5$\times$v，j=4$\times$w时，每项减去4$\times$v（这个减去k$\times$v没有实际意义，只是举例说明存在很大重复项，可以使用双端队列降低计算复杂度，后在代码中有体现这个思想），就得到：

  j = 6$\times$ w: f(6$\times$w)-6$\times$v、f(5$\times$w)-5$\times$v、f(4$\times$w)-4$\times$v 这三个中的最大值
  j = 5$\times$w: f(5$\times$w)-5$\times$v、f(4$\times$w)-4$\times$v、f(3$\times$w)-3$\times$v 这三个中的最大值
  j = 4$\times$w: f(4$\times$w)-4$\times$v、f(3$\times$w)-3$\times$v、f(2$\times$w)-2$\times$v 这三个中的最大值

很明显，要求最大值的那些项，有很多重复。根据这个思路，可以对原来的公式进行如下调整：假设d = w[i]，a = j / d，b = j % d，即 j = a * d + b，代入状态转移方程，并用k替换a - k得：

$$dp[i][j] = \max { dp[i - 1][b + k \times d] - k \times v[i] } + a \times v[i] (a – m[i] \le k \le a)$$

意思就是求j前面的$m[i]+1$ 个 数对应的 $dp[i - 1][b + k \times d] - k \times v[i]$的最大值，然后加上 $a\times v[i]$就是$dp[i][j]$。这个求最大值的过程便可以使用双端队列求解。这样算法的复杂度即降到$O(nW)$，代码如下：

//输入
int n, W;
int w[MAX_N], v[MAX_N], m[MAX_N];

int dp[MAX_W + 1]; //DP数组（循环使用）
int deq[MAX_W + 1]; //双端队列（保存数组下标）
int deqv[MAX_W + 1]; //双端队列（保存值）

void solve()
{
	for(int i=0;i<n;i++)
	{
		for(int a=0;a<w[i];a++)
		{
			int s=0, t=0; //双端队列的头部和尾部
			for(int j=0;j*w[i]+a<=W;j++)
			{
				int val = dp[j*w[i]+a] - j*v[i];//这里就是上面那个举例的思想，减去k*v[i],之后保存到双端队列中重复利用
				while(s<t && deqv[t-1]<=val) t--;
				deq[t] = j;
				deqv[t++] = val;
				dp[j*w[i]+a] = deqv[s] + j*v[i]; //加回来
				if(deq[s] == j - m[i])
				{
					s++;
				}
			}
		}
	}
	printf("%d\n", dp[W]);
}

2.3.3 区间DP

Bribe the Prisoners

有t 组测试数据，每组数据中有n个人在监狱，想要放出m个人，每放出一个人，他周围的人（两边连续的直到碰到空的监狱或者尽头）都要贿赂1块钱，没放出一个人就对应地空出一个空监狱。问最少的总花费。

考虑释放在囚犯A[i]到囚犯A[j]（不包括两端的囚犯）的囚犯时，所需的金币是释放其中$(A[i],A[j])$中一人A[k]所需的$A[j]-A[i]-2$，加上释放$(A[i],A[k])$和$(A[k],A[j])$中想要放出的囚犯所需的金币，要最小化总花费也就是要最小化释放(A[0],A[n+1])中想要释放的囚犯所需的金币。用DP来解决问题，定义

$$dp[i][j]:=释放在囚犯A[i]到囚犯A[j]（不包括两端的囚犯）中想要释放的囚犯时，所需的最小金币总数。$$

则有状态转移递推关系如下（因为不包括两端的囚犯所以是减2）：

$$dp[i][j] = \min(dp[i][k]+dp[k][j]| 1<k<j) + A[j]-A[i]-2$$

为了方便，我们把两端也加入，这样变为A[0]=0, A[m+1]=n+1。初始化最小的区间即$dp[i][i+1] = 0$。

代码如下：

#include<stdio.h>
#define INT_MAX 0x3f3f3f3f
using namespace std;
int n,m ;
//区间动态规划
//bribe the prisoner
//定义一个二维数组。依次用来填充最小的花费。
int dp[109][109];//表示从第i个填充到j个时的最小花费。
//同时定义一个存放罪犯的数组。
int a[109];
void solve()
{
    a[0]=0;
    a[m+1]=n+1;//为了解决边界问题。
    for(int i=0; i<=m; i++)
        dp[i][i+1]=0;//初始化，因为所有的从i到i+1的花费除去边界都是0；
    //循环求解。定义w表示区间的范围，w=2表示跨度为2的情况，也就是该区间里面只有一个要释放的犯人
    for(int w=2; w<=m+1; w++)
    {
        //每次选的范围都是w，从i到j 的范围内的最小值等于从i到K加从第k到j的最小值。
        for(int i=0; i+w<=m+1; i++)
        {
            //此处用到的k恰是其中的中值。
            int j=i+w,tmp=INT_MAX;//tmp用来保存当前区间的当前最好情况的花费金币数
            for(int k=i+1; k<j; k++)
                tmp=min(tmp,dp[i][k]+dp[k][j]);
            dp[i][j]=tmp+a[j]-a[i]-2;//此处就是当前区间最小值。
        }
    }
    printf("%d\n",dp[0][m+1]);
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1; i<=m; i++)
        scanf("%d",&a[i]);
    solve();
    return 0;
}

---

最大连续子序列

Bribe the Prisoners:

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

这是一个用于求解最大连续子序列和问题的最优算法。对于一个长度为n的数组A而言，从A[0] 到 A[j] 是一个子数组（j

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

class Solution { public: int maxSubArray(vector<int>& nums) { vector<int>::iterator it = nums.begin(); int maxSum = *it; int theSum = *it; for(it = it+1 ; it != nums.end(); it++){ theSum = max(theSum + *it, *it); if(theSum > maxSum) maxSum = theSum; } return maxSum; }

该法的复杂度是O(n)。