运营百科

baike

首页 > 行业资讯 > 运营百科 > 正文内容

运营百科

给我一个机会给你讲懂DP_知乎_(dp代运营是什么意思)

iseeyu4年前 (2022-10-10)运营百科415

在互联网人漫长的刷题历程中，动态规划(Dynamic Program) 绝对是一块绕不开且难啃的硬骨头。然而近年来面试官偏偏喜欢考 dp，且大有递增之趋势。

我也挣扎了很久才勉强摸清楚这类题该怎么思考，看了很多“不讲人话”的书籍和网课后，为了不让你们再经受折磨，总结了一点点心得。

想学啊？我教你啊！

一、动态规划的题目特点

计数有多少种方式走到右下角有多少种方式选出 k 个数使得和是 sum

2. 求最大最小值

从左上角走到右下角的最大数字和求最长上升子序列长度

3. 求存在性

取石子游戏，先手是否必胜能不能选出 k 个数使得和为 sum

4.其他（如博弈论等）

并不是说这三种问题出现了一定是动态规划，也有可能是贪心等等。但是动态规划的题目大部分都是这三种情况，可以往 dp 考虑

二、怎样用动态规划去解题

下文将以 Coin Change 为例，为读者讲述采用动态规划时应该怎么做

动态规划组成部分一：确定状态

状态数组决定了动态规划的状态方程应该怎么写，具有“定海神针”的作用

简单的说，解动态规划时会开一个数组，我们自己要明确 dp[i] 或 dp[i] [j] 是代表什么意思

确定状态需要两个意识

最后一步子问题

1.最后一步

虽然我们不知道最优策略是什么，但是最优策略肯定有 K 枚硬币 a1, a2, ..., ak 加起来面值为27

也就是一定存在最后那一枚硬币 ak

除去这枚硬币以后，前面的硬币加起来面值就变成了 27-ak

关键点1

我们不关心前面的k-1枚硬币怎么样拼出来的27-ak(不管是1种或者是成百上千种方法拼出来的)，而且尽管我们还不知道 ak 和 k 的具体数值，但是我们能够确定前面的硬币是 27-ak

其实这也是传说中的 “无后效性” 的意思,百度百科对于这个词的解释是这样的：

无后效性是指如果在某个阶段上过程的状态已知，则从此阶段以后过程的发展变化仅与此阶段的状态有关，而与过程在此阶段以前的阶段所经历过的状态无关。

感觉是说了句正确的废话。我想用一个例子来说明一下：

假设现在有个棋盘的左上角有颗棋子，只能往右或者往下走，问到右下角有多少种走法。对于某个位置(i,j)，我们不关心它是怎么走到这里，只知道它要么从上面来，要么从下面来，且是两条路中更短的一条中来，这就够了。如果换种问法，可以上下左右走，但是不能重复。如此，我们就不得不考虑之前走过了哪些路，这就叫后效性。

关键点2

因为是最优策略，所以拼出27-ak的硬币数一定要最少，否则就不是最优策略

假设前面的硬币只用了 K-2 枚硬币就拼出来了，那么加上最后那一枚就是 K-1 枚硬币，与假设产生了矛盾

关键点3

或许你可能知道这题要用 dp 了，但是却纠结开几维数组？在没有丰富的刷题经验之前，可以粗暴地这样理解：题目的问题是[多少]个，还是走到 [i] [j] 位置，前者一维，后者二维

2.子问题

基于上述的讨论，我们现在要求的是问题是：最少用多少枚硬币可以拼出27-ak？

而原问题是：最少用多少枚硬币可以拼出27-ak？

可以看到，原问题被转化成了一个子问题，且规模变小了

我们把问题一样，但是规模更小的问题，称之为子问题

然而，我们还不知道最后那枚硬币ak是多少！

可是！最后那枚硬币只可能是2，5，7中的一个啊！

具体 f(27) = 什么呢？因为要求的是最少的硬币数，所以：

f(27) = min(f(27-2), f(27-5), f(27-7)) + 1，加1是因为要算上第 k 枚硬币

到了这里，这题的代码已经可以写了。如果是递归的话，伪代码大致可以写成这样：

public int f(int x){ if(x == 0) return 0; int res = MAX_VALUE; if(x >= 2) res = Min( Min(f(x-2), f(x-5), f(x-7))+1, res); return res; }

不过很明显递归中有大量的重复计算，像这个问题很轻松就可以造成栈溢出

动态规划组成部分二：转移方程

状态f[x] = 最少用多少枚硬币拼出 x

对于任意x，f[x] = min{f[x-2], f[x-5], f[x-7]} + 1

最值型：就会用到min、max；计数型：+++；存在型：or、and

动态规划组成部分三：初始条件和边界情况

边界条件：如果数组的下标小于0怎么办？如f[-1]，f[-5]，对于本题，我们的策略是如果索引 Y 是负数，我们就让 f[Y] = +∞

所以 f[1] = min{f[-1], f[-4], f[-5]} + 1 = ∞+1 = ∞，表示拼不出来1，符合题意

初始条件：对于本题是f[0] = 0

如果你有一定的刷题经验你会发现，在一些题目中我们会看到有时我们会定义 f[0] ，f[1]，f[2] ，这样的初始条件，有时又不会写初始条件

具体何时写呢？

——用状态转移方程算不出来，但是又用得到值的情况时，需要手工定义。

比如这题，f[0] 如果用状态转移方程来算，f[0] = min{f[-2], f[-5], f[-7]} + 1 = ∞+1 = ∞，但是我们明明知道 f[0] 本该等于0，所以需要显示地做出定义。而 0 之后的值就不需要手工定义了

总结来看，初始条件就是定义最小的那些情况，边界条件就是为了不要让数组越界（包括上下溢）

动态规划组成部分四：计算顺序

在前面的概念都搞清楚了是不是就结束了呢？

非也

我们是应该按 f[27]，f[26]，f[25] 的顺序计算呢，还是按 f[0]， f[1]， f[2] 的顺序？

对这题来说，我们应该从小到大来计算。而且很多的 dp，包括一维二维都是从小到大，从上到下从左到右来进行递推的

计算顺序的确定只有一个原则，当要计算 f[x] 时，等号右边的式子包含的变量都已经被计算过了

对于这题，f[x] = min{f[x-2], f[x-5], f[x-7]} + 1，那么我们就得保证右边的 f[x-2]，f[x-5]，f[x-7] 都已经被算过了，否则无法算出 f[x]

时间复杂度：O(N*M)，N 是要拼出的面值，M 是硬币数。这一题就是 27 * 3

空间复杂度：O(N)，这题就是 O(27)

下面给出这题的代码，注释部分是我一开始出错的（我也不晓得为什么才超 46%，这类题代码大同小异，稍微改进一点就可以超过很多人）：

class Solution { public int coinChange(int[] coins, int amount) { int[] dp = new int[amount+1]; // Arrays.fill(dp, -1); 为什么不能用-1呢，因为一直在取min，导致数组内容一直不能被正常更新 Arrays.fill(dp, Integer.MAX_VALUE); // Arrays.fill(dp, amount+1); 也可 dp[0] = 0; for(int i = 1; i <= amount; i++){ for(int j = 0; j < coins.length; j++){ //dp[27] = min(dp[27-1]+1,dp[27-3]+1,dp[27-5]+1) if(i-coins[j]>=0 && dp[i-coins[j]] != Integer.MAX_VALUE){ dp[i] = Math.min(dp[i], dp[i-coins[j]] + 1); } } } return dp[amount] == MAX_VALUE ? -1 : dp[amount]; } }