动态规划

动态规划(Dynamic Programming),将一个复杂问题分解为几个子问题,通过综合子问题的最优解来得到原问题的最优解。DP 会将每个求解过的子问题的解记录下来,这样就可以直接使用之前记录的结果,而不用重复计算。这是动态规划提高效率的方式,但不是其核心。

一般可用“递归”或“递推”的写法来实现动态规划。

斐波那契数列的递归写法:


int F(int n){

if(n==0 || n==1) return 1;

if(dp[n] != -1) return dp[n];

else{

dp[n] = F(n-1) + F(n-2);

return dp[n];

}

}

递推写法、状态转移方程

数塔问题:第 n 层有 n 个数字,现在从第 1 层走到第 n 层,每次只能走向下一层连接的数字中最大者,问将所有路径上数字和最大是多少?

二维数组 f[i][j] 表示第 i 层第 j 个数字:f[1][1]=5, f[2][1]=8, f[2][2]=3

关键:dp[i][j] 表示第 i 行第 j 个数字到达底层所有路径中的最大和,例如dp[3][2]就是图中 7 到底层的最大和。定义这个数组后,最终的dp[1][1]就是想要的答案。

dp[1][1]是如何得到的呢?是第二层dp[2][1]dp[2][2]的最大者(第二层到底层的最大路径长度)加它自己的值f[1][1]

我们称dp[i][j]为问题的状态,把上面的式子成为状态转移方程

注意dp[i][j]实际只和下层连接的 2 个节点的状态有关,随着层号的增大,什么时候到头呢?最后一层dp[i][j]==f[i][j],这种直接可以确定其结果的部分叫作边界。从最底层的 dp 值开始,不断往上求出每一层各位置的 dp 值,最后可以得到dp[1][1],即为想要的答案。

综上所述:动态规划的递推写法,总是从边界出发,通过状态转移方程扩散到整个 dp 数组。

代码如下:


#include <cstdio>

#include <algorithm>



using namespace std;

const int maxn = 1000;

int f[maxn][maxn], dp[maxn][maxn];



int main(){

int n;

scanf("%d", &n);

for(int i = 1; i <= n; i++){

for(int j = 1; j <= n; j++){

scanf("%d", &f[i][j]); // 输入数塔

}

}



// 边界

for(int j = 1; j <= n; j++){

dp[n][j] = f[n][j]; // 最后一层dp 值等于自身

}



// 往上递推

for(int i = n-1; i >= 1; i--){

for(int j = 1; j <= i; j++){

// 状态转移方程

dp[i][j] = max(dp[i+1][j], dp[i+1][j+1]) + f[i][j];

}

}



printf("%d\n", dp[1][1]);

return 0;

}

递推和递归的区别:

显然递归可以从dp[1][1]开始,直达边界返回,是自顶向下的,从目标问题开始,分解子问题,直到分解至边界为止。而递推是自底向上的,从边界开始,不断向上解决问题,直到解决目标问题。

如果一个问题的最优解可以由其子问题的最优解改造出来,那么称这个问题具有最优子结构。一个问题必须具有“重叠子问题”,以及“最优子结构”,才能使用动态规划 DP 去解决。

分治、贪心、动态规划的区别

一、分治和动态规划的区别

两者都是分解为子问题,然后合并子问题。但是分治分解出的子问题是不重叠的,而动态规划拥有重叠子问题。比如归并排序和快速排序(分治思想):子问题(左右序列)是完全隔离的,不重叠。还有分治法解决的不一定是最优化问题,而动态规划解决的一定是最优化问题。

二、贪心和动态规划的区别

贪心和动态规划都要求原问题具有最优子结构。区别在于贪心法采用“自顶向下”但不等待子问题求解完毕后再选择哪一种,而是通过一种策略直接选择一个子问题去求解,没被选择的子问题就被抛弃不去求解了。贪心法总是基于上一步再进行选择,是一种“近似解法”,整个过程以一种单链的流水方式进行,实际上这种最优选择策略要进行归纳法证明,不是什么策略都能得到最优解:比如数塔问题从最上层开始,策略是选择下层2个数最大的那个节点,最终结果不一定是最大和。

背包问题

背包问题是经典的动态规划问题,灵活、变体多样。有两种最简单的背包问题:$01$背包、完全背包问题。完全背包问题作为NP完全问题,暂时不存在多项式时间算法。

NP完全或NP完备(NP-Complete,缩写为NP-C或NPC),是计算复杂度理论中,决定性问题的等级之一。NPC问题,是NP(非决定性多项式时间)中最难的决定性问题。因此NP完备问题应该是最不可能被化简为P(多项式时间可决定)的决定性问题的集合。若任何NPC问题得到多项式时间的解法,那此解法就可应用在所有NP问题上。

一个NPC(NP完全)问题的例子是子集合加总问题,题目为:给予一个有限数量的整数集合,找出任何一个此集合的非空子集且此子集内整数和为零。 意即:$S$ 是一个包括若干整数的集合,找出任意一个 $S’\subset S$ 且 $\sum_{x \subset S’}x = 0$。这个问题的答案非常容易验证,但目前没有任何一个够快的方法可以在合理的时间内(意即多项式时间)找到答案。只能一个个将它的子集取出来一一测试,它的时间复杂度是 $O(2^n)$,$n$ 是此集合的元素数量。

01 背包问题

有 $n$ 件物品,每件物品的重量是 $w[i]$,价值为 $c[i]$。现有一个容量为 $V$ 的背包,人如何选取物品放入背包,使得背包内物品总价最大,其中每种物品都只有 1 件。

样例:


5 8 // n==5, V==8

3 5 1 2 2 // w[i]

4 5 2 1 3 // c[i]

重要的还是搞清楚是如何状态转换,以及得到dp数组合适的意义

状态转换:不放第 i 件物品,则问题转化为前 i-1 件物品恰好装入容量为 v 的背包中所能获得的最大价值,即$dp[i-1][v]$;放第 i 件物品,则问题转化为前 i-1 件物品恰好装入容量为 v-w[i] 的背包中所能获得的最大价值,即$dp[i-1][v-w[i]] + c[i]$

我们往往是令dp值为所求的结果(最大重量),主要是各个维度的意义:什么的最大重量?

这里令dp[i][v]表示前 i 件商品恰好装入容量为 v 的背包中所能获得的最大值

状态转移方程:

注意$dp[i][v]$的状态只与$dp[i-1][]$有关,所以可枚举 i 从 1 到 n,v 从 0 到 V,通过边界 $dp[0][v]=0$($0\le v \le V$)(前0件放入任何容量的背包中都只有价值0),可以把整个 dp 数组递推出来。由于 $dp[i][v]$ 表示的是恰好为 v 的情况,所以只要枚举 $dp[n][v] (0\le v \le V)$,取其最大值才是最后的结果。

代码:


// dp[0][] 都设为 0



for(int i = 1; i <=n i++){

// i 之前的 dp 数组已经都算出来了

for(int v = w[i]; v <= V; v++){ // v=w[i]开始才有意义

dp[i][v]=max(dp[i-1][v], dp[i][v-w[i]] + c[i])

}

}

空间复杂度还可以优化,即采用“滚动数组”方式。

动态规划是如何避免重复计算的问题在 $01$背包中非常明显,暴力做法枚举每件物品放或不放入背包,忽略了第 i 件物品放或者不放而产生的最大值是完全可以由前 i 件物品的最大值决定的。

此类也称为“多阶段动态规划问题”:每个阶段的状态之和上一阶段的状态有关。$01$背包中的每个物品都可以看做一个阶段,这个阶段中的状态有$dp[i][0] \sim dp[i][V]$,它们均由上一个阶段的状态得到。事实上,对能够划分阶段的问题来说,都可以尝试把阶段作为状态的一维,这样能够更方便地得到满足无后效性的状态。如果当前设计的状态不满足无后效性,那么不妨把状态进行升维,即增加一维或若干维来表示相应信息,这样可能就满足无后效性了。

无后效性:是指如果在某个阶段上过程的状态已知,则从此阶段以后过程的发展变化仅与此阶段的状态有关,而与过程在此阶段以前的阶段所经历过的状态无关。利用动态规划方法求解多阶段决策过程问题,过程的状态必须具备无后效性。

完全背包问题

有 $n$ 件物品,每件物品的重量是 $w[i]$,价值为 $c[i]$。现有一个容量为 $V$ 的背包,人如何选取物品放入背包,使得背包内物品总价最大,其中每种物品都有无穷多件。

状态转移方程:

和$01$背包状态转移方程唯一的区别在于:$max$ 第二个参数是$dp[i]$而不是$dp[i-1]$,即选择了第 i 件产品后,还可以继续选择第 i 件产品。