[Python-闫式DP]

闫式DP分析法

闫老师是将DP问题归结为了有限集合中的最值问题。

动态规划有两个阶段，一是状态表示，二是状态计算。

状态表示 f(i,j)

状态表示是一个化零为整的过程，动态规划的做题思路不是暴力法的每一个物品都去枚举，而是将相似的物品化为一个子集作为一个整体，然后每个整体去枚举。

在状态表示中，我们需要知道f(i, j)代表的是什么集合，也就是动态规划五部曲中的明确dp数组的[i][j]代表的是什么。然后这个集合的属性是什么呢，对应到动规五部曲中就是dp数组的值。属性一般有三种，一般是最大值、最小值以及数量。

状态计算

状态计算就对应了化整为零的过程，是将集合f(i,j)分为若干个子集，划分需要满足两个准则，一是不重复，二是不遗漏。

划分的依据是：寻找最后一个不同点。

1.01背包

下面按照卡码网上的例题来试着用闫式DP分析一下。携带研究材料（第六期模拟笔试）

朴素分析

这个题目是要找在行李空间为N时的所带物品的最大价值V，也就是说有限集合中的最大值问题。这样就可以用闫式DP分析法了。

状态表示

先进行状态表示，背包问题是一种选择问题，这类问题集合的第一维一般都是选择前i个物品，后面几维一般是限制。在这道题中，第一维就是i，第二维是所带行李体积的限制j，即f[i][j]。这个集合就是所有考虑前i个物品，且总体积不超过j的选法的集合。

然后再来看值，值的选择就要看题目了，题目问的是什么，值就是什么。这个题目中要求最大价值，因此值就为每个集合中的最大值。那么题目所要求的答案就是f[N][V]，是什么意思呢？就是从前N个物品中选，在体积小于等于j时的最大价值。

因此，我们明确了f(i, j)为所有考虑前i个物品，且总体积不超过j的选法中的最大值。

状态计算

状态计算前面说了是化整为零的过程，我们现在需要求出集合f(i, j)的值，题目中就是求最大值，怎么求呢？一般是把集合划分为不同的子集，怎么划分呢？一般是找最后一个不同点。

这里的不同点其实就是是否选择最后一个物品i。即不选择物品i的所有方案与选择物品i的所有方案两种集合。这里显然不重复也不遗漏。

这样，如果要求集合的最大值的话，我们只需要求出左边集合的最大值与右边集合的最大值，再求出两者的最大值即可。

左边子集的最大值如何求？我们要从定义去求。

已知左边集合代表的是所有不选物品i的集合，也就是说范围为0 ~ (i - 1)且<= j，即f(i - 1, j),因为前面已经定义好了这个集合的值就为满足当前条件下的最大价值。

再来看右边子集。

右边子集为所有包含物品i的选法。也就是说范围为0 ~ (i - 1) & i这个意思是说，物品i是一定在选择的物品中的，其余则需要在前i - 1个物品中选。正因为物品i已经固定要选了，所以其前i - 1个物品的体积限制在<= j - weight[i]。

因此右边子集的最大值为f(i - 1, j - weight[i]) + value[i]

综上，朴素方法的状态计算为f[i][j] = max(f[i - 1][j], f[i - 1][j - weight[i]] + value[i])

代码实现

分析之后，接下来就是写代码了。

在遍历的过程中，依旧是先物品后背包的顺序进行遍历，同时由于右边子集其实是有使用范围即j >= weight[i]的，因此需要进行if判断，这里简单的写法是，先赋值左边子集的最大值，然后判断，如果在使用范围内，则取两者最大值。代码如下：

M, N = map(int, input().split())

weight = [0]
value = [0]

weight += list(map(int, input().split()))
value += list(map(int, input().split()))


f = [[0] * (N + 1) for _ in range(M + 1)]

for i in range(1, M + 1):
    for j in range(N + 1):
        f[i][j] = f[i - 1][j]
        if j >= weight[i]:
            f[i][j] = max(f[i][j], f[i - 1][j - weight[i]] + value[i])

print(f[M][N])

空间优化

朴素写法的f数组为二维的，但实际上我们需要的只是最后一行，那么就可以压缩一下变为一维数组。

朴素写法的状态计算为f[i][j] = max(f[i - 1][j], f[i - 1][j - weight[i]] + value[i])

如果压缩的话，就应该写成f[j] = max(f[j], f[j - weight[i]] + value[i])

注意这里的右边子集为j - weight[i]是一个小于j的数，我们在朴素写法时新的一行需要从上一行读出，但如果只在一行里更新的话，如果还是正常的从左向右遍历，那么就会使新的值更新到这一行中，我们需要从右向左遍历，才能让新的值不会影响这一行的值。即for j in range(N, weight[i] - 1, -1),这里也恰好保证了在满足右边子集的情况下，当前的最大值等于左边子集与右边子集两者的最大值。当不满足右边子集使用范围的情况下，当前的最大值保持上一行的值不变。

代码如下：

M, N = map(int, input().split())

weight = [0]
value = [0]

weight += list(map(int, input().split()))
value += list(map(int, input().split()))

f = [0] * (N + 1)

for i in range(M + 1):
    for j in range(N, weight[i] - 1, -1):
        f[j] = max(f[j], f[j - weight[i]] + value[i])

print(f[N])

2.完全背包

完全背包问题与01背包问题的区别在于01背包的每个物品只能取一次，而完全背包的每个物品可以取无数次，下面来推导一下。

状态表示`f[i][j]`

集合是所有只从前i个物品中选，总体积不超过j的方案的集合。

属性就是最大值。

状态计算

由于完全背包是可以无限次选择一个物品的，因此在划分子集时，不同点就在于选择物品i的个数。划分如下：

分割之后的f(i,j)为：(下面的weight数组用W代替，value数组用V代替)

f[i][j] = max(f[i - 1][j], f[i - 1][j - W[i]] + V[i], f[i - 1][j - 2*W[i]] + 2*V[i], ..., f[i - 1][j - k*W[i]] + k*V[i])

这样求显然非常不容易，加上循环的话时间复杂度又上去了。因此可以换一个角度。

f[i][j - W[i]] = max(f[i - 1][j - W[i]], f[i - 1][j - 2*W[i]] + V[i], f[i - 1][j - 2*W[i]] + 2*V[i], ..., f[i - 1][j - k*W[i]] + (k - 1)*V[i])

有点类似于移位相消法，上面的每一项都要比下面的每一项多一个V，所以上面的最大值就等于下面的最大值加一个V，所以f[i][j] = max(f[i - 1][j], f[i][j - W[i]] + V[i])

朴素写法

N, V = map(int, input().split())
w = [0] * (N + 1)
v = [0] * (N + 1)
for i in range(1, N + 1):
    w[i], v[i] = map(int, input().split())

f = [[0] * (V + 1) for _ in range(N + 1)]

for i in range(1, N + 1):
    for j in range(1, V + 1):
        f[i][j] = f[i - 1][j]
        if j >= w[i]:
            f[i][j] = max(f[i][j], f[i][j - w[i]] + v[i])

print(f[N][V])

空间优化

N, V = map(int, input().split())

w = [0] * (N + 1)
v = [0] * (N + 1)

for i in range(1, N + 1):
    w[i], v[i] = map(int, input().split())

f = [0] * (V + 1)

for i in range(1, N + 1):
    for j in range(w[i], V + 1):
        f[j] = max(f[j], f[j - w[i]] + v[i])
        
print(f[V])

01背包、完全背包小结

01背包：f[i][j] = max(f[i - 1][j], f[i - 1][j - weight[i]] + value[i])

完全背包：f[i][j] = max(f[i - 1][j], f[i][j - weight[i]] + value[i])

下面再来看看例题。以蓝桥官网中的游戏中的学问为例。

游戏中的学问

题目描述

大家应该都见过很多人手拉手围着篝火跳舞的场景吧？一般情况下，大家手拉手跳舞总是会围成一个大圈，每个人的左手拉着旁边朋友的右手，右手拉着另一侧朋友的左手。

不过，如果每一个人都随机的拉住两个不同人的手，然后再慢慢散开，事情就变得有趣多了——此时大家依旧会形成圈，不过却可能会形成多个独立的圈。当然这里我们依然要求一个人的右手只能拉另一个人的左手，反之亦然。

班里一共有 NN 个同学，由 11 到 NN 编号。Will 想知道，究竟有多少种本质不同的拉手方案，使得最终大家散开后恰好形成 kk 个圈呢？

给定两种方案，若存在一个人和他的一只手，满足在这两种方案中，拉着这只手的人的编号不同，则这两种方案本质不同。

输入描述

输入一行包含三个正整数N,k,PN,k,P。

其中，3≤k≤N≤30003≤k≤N≤3000，104≤p≤2×109104≤p≤2×109。

输出描述

输出一行一个整数，表示本质不同的方案数对 pp 的余数。保证 pp 一定是一个质数。

解题思路

首先先状态表示。

这里设集合为f[i][j]，为i个同学围成j个圈的方案集合。属性为方案的总数。

再状态计算。

先要把集合划分，到第i个同学时的不同点就是在已有圈中加入同学i，以及同学i和原来圈中抽出两个同学再组成一个新的圈。再来想想，这种划分方法达到了不重复、不遗漏了吗？为什么原来圈中不能抽出来3个同学与同学i组成一个新的圈呢？

因为如果是抽出三个同学再组成新圈的话，这个其实是与已有圈中加入同学i重复，这时已有的圈肯定会有三个同学围成的圈，这个要考虑清楚。因此划分为在已有圈中加入同学i与在原来圈中抽出2个同学与同学i围成新圈是不重复不遗漏的。

首先来看在已有圈中加入同学i。已知目前有i个同学，那么已有圈中有i - 1个同学，也就是有i - 1个边，我们如果想要加入同学i的话，可以在i - 1个边中加入，因此方案数有(i - 1) * f[i - 1].

再来看一下右边子集，同学i与原来圈中抽出两个同学组成一个新圈。抽出两个同学的话，那么已有圈就只剩下i - 3个同学了，而且要组成一个新圈之后才有j个圈，所以目前是有j - 1个圈的，即f[i - 3][j - 1],从i - 1个同学中不放回的抽取2个同学，一共有C^2(i - 1)个方案数，再组成新圈，要记得组成三个人的新圈也是有两种情况的，所以还要乘以2，因此右边子集的情况就为：f[i - 3][j - 1] * (i - 1) * (i - 2)

要时刻记得集合的含义！这里不是两者求最大，而是求在这两种情况下的方案数之和，才是集合的方案数总和。我们要求的属性是方案数总和！代码如下：

N, k, P = map(int, input().split())

f = [[0] * (k + 1) for _ in range(N + 1)]
f[3][1] = 2 #初始状态

for i in range(4, N + 1): 
  for j in range(1, k + 1):
    f[i][j] = (((i - 1) * f[i - 1][j]) % P + ((i - 2) * (i - 1) * f[i - 3][j - 1]) % P) % P

print(f[N][k])

518. 零钱兑换 II

给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。

请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。

假设每一种面额的硬币有无限个。

题目数据保证结果符合 32 位带符号整数。

解题思路

明显这个题是完全背包。

首先来看状态表示。设dp[i][j]为取前i个硬币下总金额为j的方案总数。

再来看状态计算，将dp[i][j]集合划分，由于是完全背包可以取无限次，因此可以大体分为取i和不取i。不取i的情况就是dp[i - 1][j] ,取i的情况有无限种，但可以转化为dp[i][j - V[i]]，具体推导在上面已经说过。

求方案数时，初始化一般都会把dp[0]初始化为1，从而后面才会是有效的次数。

所以集合dp[i][j] = dp[i - 1][j] + dp[i][j - V[i]]

空间优化就是从小到大遍历的dp[j] = dp[j] + dp[j - V[i]]代码如下。

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        dp = [0] * (amount + 1)
        dp[0] = 1
        for i in range(len(coins)):
            for j in range(coins[i], amount + 1):
                dp[j] = dp[j] + dp[j - coins[i]]
        return dp[-1]

这个题是求的组合数，因此重复的集合会算作一个，遍历顺序就是先物品再背包，这样能够保证集合的唯一性，因为物品在这种遍历下不能颠倒顺序。

377. 组合总和 Ⅳ

给你一个由不同整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。

题目数据保证答案符合 32 位整数范围。

解题思路

这个题乍一眼看和上面很像，但还是有区别的，在于这里的组合可以颠倒顺序，即排列数。排列数就要要求遍历顺序为先背包后物品，因为这样可以使物品的顺序发生颠倒。下图为例：

其他都一样，代码如下：

class Solution:
    def combinationSum4(self, nums: List[int], target: int) -> int:
        dp = [0] * (target + 1)
        dp[0] = 1
        for i in range(1, target + 1):
            for j in range(len(nums)):
                if i >= nums[j]:
                    dp[i] = dp[i] + dp[i - nums[j]]
        return dp[-1]