动态规划

文章目录

• 前言
• 一、动态规划是什么？
• 二、动态规划的核心思想
• 三、例题解答

前言

上周的上机题目中有一道题目是“分宝物”，这道题虽说是1星题目，但考察的点还是很有意思的。这道题是简易版的“分配宝藏”，之后应该会遇到的。

很显然，这是一道关于动态规划（ Dynamic programming ）的问题。动态规划问题非常非常经典，也很有技巧性。

今天跟一起来学习一下动态规划，文章如果有不正确的地方，欢迎大家联系我指出错误哈，感谢~

一、动态规划是什么？

动态规划（英语：Dynamic programming，简称 DP），是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。动态规划常常适用于有重叠子问题和最优子结构性质的问题。

以上定义来自于百度百科动态规划。从定义来看的话，有点儿抽象，不便于理解。简单来说，动态规划其实就是，给定一个问题，我们把它拆成一个个子问题，直到子问题可以直接解决。然后呢，把子问题的答案保存起来，以减少重复计算。再根据子问题答案进行反推，得出原问题解的一种方法。

一般来说，这些子问题都十分相似，可以通过函数关系式递推出来。然后呢，动态规划就致力于解决每个子问题只解决一次，减少重复计算。

比如斐波那契数列就可以看做入门级的经典动态规划问题（斐波那契数列的例子严格来说不算动态规划，因为没有涉及求最值，所以该篇文章主要是讲解如何从斐波那契数列理解动态规划）。

二、动态规划的核心思想

动态规划最核心的思想，就在于拆分子问题，记住子问题的解，减少重复计算。

什么意思呢？我们先来看下，网上比较流行的一个例子：

A ："1+1+1+1+1+1+1+1 =？"

A ："上面等式的值是多少？"

B ：计算，答案是 "8"

A : 在上面等式的左边写上 "1+" 呢？

A : "此时等式的值为多少？"

B : 很快得出答案 "9"

A : "你怎么这么快就知道答案了"

A : "只要在8的基础上加1就行了"

A : "所以你不用重新计算，因为你记住了第一个等式的值8！动态规划算法也可以说是 '记住求过的解来节省时间' "

想必，看到这里你一定对动态规划的思想有了进一步的了解。接下来我们看看如何用动态规划解决斐波那契数列这个问题。

以往我们处理这个问题的时候，一般使用的是暴力递归的方法。用递归的话，很简单，对吧。但是由于递归的计算效率过低，很容易导致程序超时。下图是斐波那契数列问题的递归树：

首先，要计算原问题 f(n)，就需要先计算出子问题 f(n – 1) 和 f(n – 2)

然后，要计算 f(n – 1)，又要先算出子问题 f(n – 2) 和 f(n – 3)，以此类推······

最后，一直到 f(2) 和 f(1），递归树才会终止

我们先来看看这个递归的时间复杂度吧：

递归时间复杂度 = 解决一个子问题所需的时间 * 子问题个数

解决一个子问题所需的时间 = f(n – 1) + f(n – 2)，也就是一个加法的操作，所以复杂度是 O(1)；问题个数 = 递归树节点的总数，递归树的总节点 = 2 ^ n – 1，所以是复杂度O(2 ^ n)。

因此，利用递归法解决斐波那契数列的时间复杂度 = O(1) * O(2 ^ n) = O(2 ^ n)，就是指数级别的，爆炸增长的，如果n比较大的话，超时是很正常的。

我们回过头来仔细观察这颗递归树，不难看出，你会发现存在大量的重复计算，比如f(n -2)被计算了两次，f(n – 3)被重复计算了3次······所以这就是递归算法低效的原因，就是存在大量的重复计算！

因为计算机遇到一个子问题它只会“傻傻地”去计算，并不知道自己可能已经算过好多遍了。但是如果我们可以让计算机来“记忆”已经计算过的子问题的答案，那么就可以省去重复计算的耗时了。

基于这样的思想，我们可以使用一个备忘录，把已经计算过的子问题的答案记录在里面。每次计算前，先来备忘录看看有没有算过，如果之前算过，那就直接从备忘录中提取；如果没有，那就算一遍，然后记录到备忘录中。这就是带备忘录的递归解法（自顶向下）。

一般使用一个数组来充当这个备忘录。然后，我们画一下用了备忘录递归算法的递归树，如下：

实际上，带备忘录的递归算法，把一棵存在巨量冗余的递归树通过裁剪，改造成了一幅不存在冗余的递归图，极大减少了子问题（即递归图中节点）的个数。现在，子问题个数 = 树节点数 = n，解决一个子问题还是O(1),所以带备忘录的递归算法的时间复杂度是O(n)。接下来呢，我们用带备忘录的递归算法去写一下这个代码，代码如下：

#include<stdio.h>
#include<time.h>
 
int memo[1001] = { 0 };		//备忘录数组
 
int help(int memo[], int n) {		//定义help函数来建立备忘录
	if (n == 1) return 1;
	else if (n == 2) return 2;
	else if (memo[n] != 0) return memo[n];
	memo[n] = help(memo, n - 1) + help(memo, n - 2);
	return memo[n];
}
 
int fib(int n) {
	if (n < 2) return 1;
	else return help(memo, n);
}
 
int main() {
	
	clock_t start, finish;		//为程序计时
	start = clock();
	int n;
	
	scanf_s("%d", &n);
	printf("f(%d) = %d\n", n, fib(n));
	finish = clock();
	printf("所需时间：%f", (double)(finish - start) / CLOCKS_PER_SEC);
	
	return 0;
 
}

（由于时间关系，注释写的不是很详细，如有疑问，可以在评论区留言。后面有时间的话我会把注释补全，我也相信大家能够看懂）

下表是递归算法和动态规划分别所需时间的表格（数据有一定误差）。

n \ 算法（单位：秒）	递归	带备忘录的递归
1	0.755	0.742
5	1.030	0.810
10	1.233	0.909
20	1.311	1.110
30	2.891	1.375
40	4.444	1.281
50	345.580	1.726

不难看出，在n的值较小的时候，二者时间差很小甚至暴力递推所需时间小于带备忘录的递归。但在n值较大的时候，二者差别就很明显了。当n为50时，带备忘录的递归所需时间仅递归的1 / 344左右。

实际上，这种带备忘录的递归解法和迭代的动态规划已经差不多了，只不过这种方法叫做自顶向下，而动态规划叫做自底向上。

接下来我们来看看自底向上的动态规划解法。

首先，介绍几个动态规划中的名词：最优子结构、状态转移方程、边界、重叠子问题。

• f(n – 1)和f(n – 2) 称为 f(n) 的最优子结构
• f(n)= f(n – 1) + f(n – 2)叫做状态转移方程
• 自然，f(1) = 1, f(2) = 2 就是边界了
• 例如f(n)= f(n – 1)+f(n – 2)，f(n – 1) = f(n – 2) + f(n – 3) 等等就是重叠子问题

状态转移方程实际上就是描述问题结构的数学形式：

我们可以把 f(n) 看做一个状态 n，这个状态 n 是由状态 n – 1 和状态 n – 2 相加并且转移而来得到的，这就叫状态转移。

仔细观察的话不难发现，上面的两种种解法中的所有操作，例如暴力递归中的return f(n – 1) + f(n – 2)和memo[n] = help(memo, n – 1) + help(memo, n – 2)都是这个方程式的不同表现形式。可见列出状态转移方程的重要性，它是解决问题的核心。

我们来看下自底向上的解法，从f(1)往f(n)方向，根据以上的启发，是不是直接用一个for循环就可以解决了呢，如下：

项数	1	2	3	4	······	n – 2	n – 1	n
子问题	f(1)	f(2)	f(3)	f(4)	······	f(n – 2)	f(n – 1)	f(n)
f(n)	1	1	f(1) + f(2)	f(2) + f(3)	······	f(n – 3) + f(n – 4)	f(n – 2) + f(n – 3)	f(n – 1) + f(n – 2)

带备忘录的递归解法，空间复杂度是O(n)，但是呢，我们仔细观察上图，可以发现，f(n)只依赖前面两个数，所以只需要两个变量prev和curr来存储，即只要存储之前的两个状态就行了。所以，我们可以写出如下程序，把空间复杂度降为 O(1)：

int fib(int n) {
    if (n <= 2)
        return 1;
    long long prev = 1, curr = 1;
    for (int i = 3; i <= n + 1; ++i) {
        long long sum = prev + curr;
        prev = curr;
        curr = sum;
    }
    return curr;
}

上面的代码就是自底向上的动态规划解法。

我们再来比较一下三种算法计算所需的时间。很显然，动态规划用时最少。

n \ 算法（单位：秒）	递归	带备忘录的递归	动态规划
1	0.755	0.742	0.680
5	1.030	0.810	0.525
10	1.233	0.909	1.030
20	1.311	1.110	1.081
30	2.891	1.375	2.891
40	4.444	1.281	1.219
50	345.580	1.726	1.322

以上就是我个人对于动态规划的核心思想的看法和理解。若有不合理的地方，请在评论区留言，大家一同讨论学习。

三、例题解答

题目：

标题

分配宝藏

类别

综合

时间限制

2S

内存限制

256Kb

问题描述

两个寻宝者找到一个宝藏，里面包含n件物品，每件物品的价值分别是W[0]，W[1]，…W[n-1]。 SumA代表寻宝者A所获物品价值总和，SumB代表寻宝者B所获物品价值总和，请问怎么分配才能使得两人所获物品价值总和差距最小，即两人所获物品价值总和之差的绝对值|SumA – SumB|最小。

输入说明

输入数据由两行构成： 第一行为一个正整数n，表示物品个数，其中0<n<=200。 第二行有n个正整数，分别代表每件物品的价值W[i]，其中0<W[i]<=200。

输出说明

对于每组数据，输出一个整数|SumA-SumB|，表示两人所获物品价值总和之差的最小值。

输入样例

4 1 2 3 4

输出样例

0

解答：

#include<stdio.h>
 
int W[201] = { 0 }, sum = 0, dp[201][20001] = {0};
									
int max(int a, int b) { return a > b ? a : b; }
 
int main(void)
{
	int n, i, j, sum_A;				//假设A得到的永远是较少的那个
	scanf("%d", &n);
	for (i = 1; i <= n; i++) {		//i代指第i个物品
		scanf("%d", &W[i]);
		sum += W[i];
	}
	for (i = 1; i <= n; i++) {
		if (W[i] > sum / 2) {		//如果这件宝物的价值超过了总价值的一般，那么剩下的都给另一位，就不需要再计算了
			dp[n][sum / 2] = sum - W[i];
			break;
		}
		for (j = 1; j <= sum / 2; j++) {	//j分别代指第i个物品和背包剩余容量
			if (W[i] > j) 					//同样的，物品重量大于背包剩余容量，不偷
				dp[i][j] = dp[i - 1][j];
			else
				dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - W[i]] + W[i]);
		}
	}
	
	sum_A = dp[n][sum / 2];
	printf("%d\n", sum - 2 * sum_A);	//因为sum_A小于sum/2，所以不需要加绝对值
	
	return 0;
 
}

本文来源于我本人的的动态规划——[XDOJ]分配宝藏