闫式Dp分析法（一种求解动态规划问题的思路）

最近一直跟着Acwing学习动态规划问题的求解思想，感觉晦涩的算法问题一旦经过闫式Dp分析法的剖析，瞬时迎刃而解，故今天我觉得很有必要再次分享一下闫式Dp分析法（在此默认你对DP问题有了一定的了解）。

闫式Dp分析法

闫式Dp分析法包含了问题的状态表示与状态的计算，其中状态表示又可以细分为集合的定义以及集合的属性，而动态规划问题的最终答案就是最终所求集合的属性。

总所周知，解决DP问题一般需要定义一个二维数组f,而f的每一项f(i,j)在闫式Dp分析法中蕴含着丰富的意义。其中，集合的定义与坐标i与j之间存在直接联系，而f(i,j)的值就是该集合的属性。状态的计算脱离不了集合的划分，其中f(i,j)对应的集合set将会划分为若干个子集合 $set_{i}$ ，其中

$set = \bigcup (set_{i}) \; \; and \; set_{i} \bigcap set_{j} = \emptyset \; (i!=j)$

概念都是抽象的，下面我举出一个经典的Dp入门问题01背包问题的案例，并借助闫式Dp分析法解决它，以便让读者有更加深刻的理解.

案例分析

在阅读下面案例分析内容时，默认读者已对问题有基本了解，不再做任何问题的描述.

01背包问题

01背包问题给出N件物品何一个容量为V的背包，在每一件物品都只能使用一次的情况下，考虑一种物品的装载方案，求算出容量为V的背包所能装载物品的最大价值（每一个物品都有一个对应的价值和体积）.

直接定义二维数组f,那么我们可以这样子定义状态的表示，其中f(i,j)状态对应的集合含义为：在只考虑选择前i个物品的情况下，将前i个物品中的若干个装入背包，使其容量之和小于或等于j的所有方案.该集合的数学表示为： $set = \{set_1,set_2,...,set_{i},...\}$ .

其中 $set_{i}$ 表示其中一种物品装入背包的方案，与此同时，假设 $obj_{i},v_{i}$ 分别表示第i物品与第i个物品的体积，那么任意一个 $set_{i} = \{obj_{k}|1<=k \; and \; k<=i \; and \sum_{k=1}^{i}(v_{k})<=j \}$ .

f(i,j)表示集合某一个属性，在01背包问题中，f(i,j)表示集合中某一个元素中所有物品之和的最大值。看起来有点抽象，但是f(i,j)有如下数学公式,其中 $m_{k}$ 表示第k个物品的价值： $f(i,j) = max \sum m_{k},m_{k} \in set_{i}$

最后，我们来划分一下f(i,j)对应的集合，其实很简单。由于每一个物品只能选一次，只存在选与不选两种方案，因此集合可以划分为 $set_{k}$ 包含第i个物品或者 $set_{k}$ 不包含第i个物品.f(i,j)表示集合中某一个元素中所有物品之和的最大值,因此f(i,j)的推导公式如下： $f(i,j) = max(f(i-1,j),f(i-1,j-v_{i})+m_{i})$

最后，01背包问题的最终答案就是f(N,V)!

好了，01背包问题的闫式Dp分析法到此为止便结束了，还有更多的DP问题都能够通过闫式Dp分析法来解决。毕竟，闫式Dp分析法在大部分情况下还是很好用的，它的难点在于如何定义集合，要求集合与二维数值下标(i,j)建立起联系，与此同时要定义集合的属性，属性往往与问题的答案相互挂钩，最后是将集合划分，推算出集合属性与它的子集合属性之间的数学公式，建立起递推方程.

写在最后

阅读完上述的闫式Dp分析法后，倘若你有所领悟，你便能发现动态规划之所以省时间的原因是，它优化了暴力解决方法。

倘若使用暴力方法求解背包问题，那么由于一共有 $2^{N}$ 种物品的组合方案（每种物品有选与不选两种选择）,对于每一个方案需要求算它的体积之和以及价值之和，那么总共的时间复杂度为 $O(N*2^{N})$ .这个是一个很糟糕的时间复杂度，即使N = 1000，暴力解法的计算次数已经高达 $10^{303}$ 次。一般电脑C++每秒求算 $10^{7}$ ~ $10^{8}$ ,

即该问题基于暴力解法的最好求算时间是 $10^{295}$ 秒，大概是 $10^{280}$ 亿年！！！是不是大为震撼，地球诞辰以来还不需要如此长的时间，倘若真的使用暴力解法来求算背包问题，恐怕要计算到宇宙爆炸，你的生命等不来，甚至连人类社会都等不来，哈哈！然而，倘若使用动态规划算法来求解，只需要1s,两种算法之间需要存在天壤之别！