简述动态规划

动态规划算法是把原问题视作若干个重叠子问题的逐层递进，每个子问题在求解的时候，姑且可以称为一个阶段。动态规划中，只有完成了前一个阶段的计算之后，才能执行下一个阶段的计算。 举个栗子

比如，我现在有一个数组叫做d p [ j ] dp[j]dp[j]，它的值只能够从d p [ j − x x x ] dp[j-xxx]dp[j−xxx]推导计算出来。

为了保证这些计算能够顺序的、不重复的进行，动态规划已经求解的子问题不能受后续阶段的影响。那么动态规划对状态空间的的遍历可以视作一张有向无环图，这遍历顺序就可以当做对该有向无环图的拓扑排序。有向无环图中的节点对应问题中的“状态”，图中边则对应状态间的“转移”，转移的选取就是动态规划中的“决策”。

动态规划算法把相同的计算过程作用于各阶段的同类子问题，感觉上有点像把一个高中的数列一样了。

01背包

背景

题目可以抽象出来如下描述：

有一个体积为v的背包和一堆体积为v vv，价值为w ww的物品。每件物品最多只能用1次，所以咯，对于每个物品，要么用0次，要么用1次。故称为01背包问题

例题描述

DP分析

照着y总讲授的闫式DP分析思路，照猫画虎的对01背包进行分析。

首先要清楚集合f [ i , j ] f[i , j]f[i,j]到底表示的是什么。

其次是要清楚要利用哪个属性进行求解。是最大值？还是数量？亦或是最小值.

对于背包问题了，大多数都是想要在有限的体积下获得最大的价值，所以一般是对“最大值”这个属性进行维护。

最后便是状态计算中对状态的划分，从而得到状态转移方程。

状态转移方程优化

DP中，状态分析和优化是两个环节。一般来说是先进行状态分析获得朴素版本的状态转移方程。再看能不能再对空间和时间进行优化，是在得到朴素版本之后再做的考虑。

将上图的状态计算环节总结为下图

落实到代码上即如图

朴素版的DP的状态转移方程，我们发现，每一阶段i ii的状态只会与上一个阶段的i − 1 i-1i−1有关。这种时候就可以使用滚动数组的方式进行优化，降低空间开销

落实到代码上即如图：

在上述程序中，我们把阶段i的状态存储在第一维的下标为i&1的二维数组中。当i为奇数的时候，i&1等于1；当i为偶数时，i&1等于0。因此，DP的状态就相当于在f [ 0 ] [ x x x ] f[0][xxx]f[0][xxx]和f [ 1 ] [ x x x ] f[1][xxx]f[1][xxx]两个数组中进行交替转移，空间复杂度从O ( M N ) O(MN)O(MN)降低到O ( M ) O(M)O(M)

进一步分析，容易发现，在每个阶段开始时，实际上执行了一次从f [ i − 1 ] [ x x x ] f[i-1][xxx]f[i−1][xxx] 到f [ i ] [ x x x ] f[i][xxx]f[i][xxx]的拷贝操作。当我们省略掉f ff数组的第一维。变成一维数组，即当外层循环到第i ii个物品的时候，此时f [ j ] f[j]f[j]表示背包中放入总体积为j jj的物品最大价值之和

注意上述代码中的倒序循环：

f ff数组的后半部分f [ j , m ] f[j ,m]f[j,m]处于“第i个阶段”，也就是状态计算时所做的图中的右半部分。

前半部分f [ 0 , j − 1 ] f[0,j-1]f[0,j−1]处于“第i-1个阶段”,也就是状态计算时所做的图中的左半部分。

随着j jj的不断减小，意味着我们总是用第i − 1 i-1i−1个阶段的状态向第i个阶段的状态转移，和咱们最初推导的转移方程的想法是一致的

参考代码(C++版本）

完全背包

例题描述

DP分析法

完全背包依旧可以采用01背包中的分析方式，只是因为完全背包中，每件物品可以无限使用，因此在状态分析的时候会有点不同。

在这张分析图中，核心的核心是这个集合f [ i , j ] f[i , j]f[i,j]到底表示的是什么，这决定了后续的状态计算中的对集合的划分以及最后的答案输出等等

状态转移方程优化

将上图的状态计算环节总结为下图

初值f [ 0 , 0 ] = 0 f[0 , 0] = 0f[0,0]=0,其余的f [ 0 , 1 f[0 , 1f[0,1] 、f [ 0 , 2 ] f[0 , 2]f[0,2] 等等均为无意义

背包问题中是无法再优化时间的了，目前的优化只是优化空间。能否优化取决于是否具备单调性。

直接由状态转移方程编写的d p dpdp代码如下：

对于f [ i , j ] f[i,j]f[i,j] = f [ i − 1 , j ] f[i -1 ,j]f[i−1,j]而言：

等式先计算右边的f [ i − 1 , j ] f[i -1 ,j]f[i−1,j]，再将计算结果赋值存放到f [ i , j ] f[i,j]f[i,j]中。现在处于i ii层循环，那么这个可以用来赋值的f [ i − 1 , j ] f[i -1 ,j]f[i−1,j]肯定是从i − 1 i-1i−1而来的，故可以直接去掉数组的第一维。

对于f [ i , j ] f[i,j]f[i,j] = m a x maxmax(f [ i − 1 , j ] f[i-1,j]f[i−1,j]，f [ i ， j − v i ] + w i f[i ，j - vi]+wif[i，j−vi]+wi)而言：

f [ i − 1 , j ] f[i-1,j]f[i−1,j]的处理方式和上面一致

j jj是从大到小遍历上来的，所有的j jj > j − v i j - vij−vi。因此，在需要用 j − v i j - vij−vi的值来就算j jj的时候，他俩肯定都处于i ii的同一层，而来数值更小的j − v i j-vij−vi已经被算出来，故f [ i ， j − v i ] + w i f[i ，j - vi]+wif[i，j−vi]+wi中的i ii可以直接去掉

优化后：

参考代码(C++版本）

/