专题: 动态规划(一)

作者 Lucyyang 日期 2022-06-20
专题: 动态规划(一)

Lucyyang又重新开始写题了,起因是这样的:

因为2022上半年的一系列事情,人生轨迹骤变,迷茫之余也有点无聊。时间一下子充足了,却干什么都有点动力缺缺,小轩表示他不能放任我这样下去,于是拉起躺在地上的我起来刷题。最开始也就每日一题,打打周赛,并没有什么目标。不过这几次周赛发现最后一题似乎能摸到边了,虽然尝试写了好几次还是没AC,不过至少是有点正向反馈了,想试着挑战一下难一点的题目了。

记录下周赛298的最后一题,经典DP的二维变形:

2312. Selling Pieces of Wood

题目:2312. Selling Pieces of Wood,给定一块长为m,宽为n的木板以及不同切法的价格,求出收益最大的价格。注意这题每次只能横切或者竖切,不存在曲里拐弯的切法,比赛的时候漏了这句,最后一小时里都在写空气。

解法:这个solution解释得特别好,有图比较直观。dp[i][j]表示长为i,宽为j的木板能拿到的最大收益。转移方式是:(1) 要么不切,完整的一块就对应的价格;(2) 横着切一刀,价格是两个小木板的和;(3) 竖着切一刀。取这三种方式中的最大值。

代码:

class Solution:
def sellingWood(self, m: int, n: int, prices: List[List[int]]) -> int:
dp = [[0 for i in range(n+1)] for j in range(m+1)]
for h, w, p in prices:
dp[h][w] = p
for h in range(1, m+1):
for w in range(1, n+1):
## horizontal cut
for hor in range(1, h//2+1):
dp[h][w] = max(dp[h][w], dp[hor][w] + dp[h-hor][w])
## vertical cut
for ver in range(1, w//2+1):
dp[h][w] = max(dp[h][w], dp[h][ver]+dp[h][w-ver])
return dp[m][n]

1770. Maximum Score from Performing Multiplication Operations

题目: 1770. Maximum Score from Performing Multiplication Operations,一道比较经典的二维dp题目。给定两个数组nums和multipliers,每次操作可以从nums的左端或者右端拿走一个数,用这个数乘以multipliers[i-1](第i次操作,题目中则定义为1-index,为和代码统一定义为0-index),最后的分数是所有操作的结果值之和,求m次操作之和最大的分数。

解法:第i次操作的结果和三个量有关:前一次(i-1)操作,前一次中从nums左边取和从nums右边取的个数,而右边取的个数可以从i次操作和左边取的个数推出。因此,我们定义二维数组dp[i][l]为第i次操作(即取了i个数),其中l个nums左端的数以及(i-l)个nums右端的数能达到的最大分数,dp[i][l]可以从(1) dp[i-1][l]加上选中的右边的值nums[n-(i-l)]乘以multipliers[i-1];(2) dp[i-1][l-1]加上选中的左边的值nums[l-1]乘以multipliers[i-1],两者中最大的一个进行转移。base case则考虑左边全不取和只取左边的情况。

代码:

class Solution:
def maximumScore(self, nums: List[int], multipliers: List[int]) -> int:
n, m = len(nums), len(multipliers)
dp = [[0] * (m + 1) for _ in range(m + 1)]
## base case
for i in range(1, m+1):
dp[i][i] = dp[i-1][i-1]+nums[i-1]*multipliers[i-1]
dp[i][0] = dp[i-1][0] + nums[n-i]*multipliers[i-1]
ans = dp[m][m]
for i in range(1, m+1):
for l in range(1, i):
dp[i][l] = max(dp[i-1][l-1]+nums[l-1]*multipliers[i-1], dp[i-1][l]+nums[n-(i-l)]*multipliers[i-1])
## optimization
if i == m:
ans = max(ans, dp[m][l])
return ans

2318. Number of Distinct Roll Sequences

题目: 2318. Number of Distinct Roll Sequences,掷n次骰子,每次得到的结果形成一个序列。如果相邻的两个值的最大公约数不为1或者位置之差在2以内的值有相同的则为不合法的序列。求解掷n次之后有多少种合法的序列。

解法:第81次双周赛的最后一题,一上来我考虑的是怎么直接通过math求解出个数,方向就不太对。赛后XXX表示数据范围是n<=10^4,如果可以直接算术求解的话,范围是可以出到很大。暂时没看到特别好discussion上的解法,看了下大雪菜的讲解, 稍微画了个图,还是比较清晰的。大概思路是:第i次合法序列的数量只和第i-1次的合法序列及其最后两位的值有关(位置之差2以内不能有相同的值),因此我们定义dp[i][j][k]为长为i并且最后两位值为j,k的合法序列个数(...j->k->end)。转移来自合法的dp[i-1][x][j],其中x是不确定的值,我们需要枚举合法的x。

代码:

class Solution:
def distinctSequences(self, n: int) -> int:
dp = [[[0 for i in range(6)] for j in range(6)] for k in range(10010)]
if n == 1:
return 6
## base case
for i in range(6):
for j in range(6):
if i!=j and self.gcd(i+1, j+1) == 1:
dp[2][i][j] = 1
for i in range(3, n+1):
for j in range(6):
for k in range(6):
if j == k or self.gcd(j+1, k+1) != 1:
continue
for x in range(6):
## valid case x
if x !=j and x != k and self.gcd(x+1, j+1) == 1:
dp[i][j][k] = (dp[i][j][k] + dp[i-1][x][j]) % 1000000007
res = 0
for i in range(6):
for j in range(6):
res = (res + dp[n][i][j]) % 1000000007
return res
def gcd(self, a, b):
if b == 0: return a
return self.gcd(b, a%b)

不过很不幸,虽然复杂度是合理的O(6^3*n),在python下还是TLE了。于是学习了一下XXX的代码,换成了cpp并且做了一下空间上的优化(每次计算当前结果只需要上一次的结果,所以每次只保留当前结果即可):

class Solution {
public:
int distinctSequences(int n) {
if (n==1) {
return 6;
}
bool v[7][7] = {};
for (int i = 1; i <=6; i++) {
for (int j = 1; j <=6; j++) {
v[i][j] = gcd(i, j) == 1 && i != j;
}
}
int Q = 1e9 + 7, cur = 0, nxt = 1;
int f[2][7][7] = {};
for (int i = 1 ; i <= 6 ; ++ i) {
for (int j = 1 ; j <= 6 ; ++ j) {
f[cur][i][j] = v[i][j];
}
}
for (int l = 3 ; l <= n ; ++ l) {
memset(f[nxt] , 0 , sizeof(f[nxt]));
for (int i = 1 ; i <= 6 ; ++ i) {
for (int j = 1 ; j <= 6 ; ++ j) {
for (int k = 1 ; k <= 6 ; ++ k) {
if (v[j][k] && k != j && k != i) {
f[nxt][j][k] += f[cur][i][j];
f[nxt][j][k] %= Q;
}
}
}
}
swap(cur, nxt);
}
int res = 0;
for (int i = 1 ; i <= 6 ; ++ i) {
for (int j = 1 ; j <= 6 ; ++ j) {
res += f[cur][i][j];
res %= Q;
}
}
return res;
}
};

还是要例行膜一下的%%%。

518. Coin Change 2

题目:518. Coin Change 2,给定一系列面额的硬币,问有多少种方案可以达到amount值,每种硬币可以无限量使用。

解法:这题咋一看可以从Coin Change的解法直接替换过来,只需要将dp[i]定义为amount为i时使用的方案数。但其实遇到了个坑,遍历时coin和i的顺序会决定了是否会算入重复的方案数。举例说明,第一次写的时候写成了:

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

假设我们硬币面额有两种1和2,如果amount为3,dp[3]则为3,因为把1+2和2+1这两种方案进行重复计算了。调换一下coin和i的顺序之后可以避免计算重复的方案数:

class Solution:
def change(self, amount: int, coins: List[int]) -> int:
dp = [0] * (amount + 1)
dp[0] = 1
for coin in coins:
for x in range(coin, amount + 1):
dp[x] += dp[x - coin]
# print(dp)
return dp[amount]

此时不存在2+1这种硬币顺序倒过来的方案了。题解中有一张示意图可以帮助理解,硬币面额分别是2,5,10: 示意图

97. Interleaving String

题目:97. Interleaving String,给定两个字符串,是否能交织形成第三个字符串。

题解:这个视频讲解得很清楚,作为一个还没熟练掌握dp字符串的人也能听得很明白,同类型的题目还有712115583。顺着大佬的思路理一下,我们还是先考虑状态转移,dp[i][j]表示s3[:i+j]能否由s1[:i]和s2[:j]交织获得。从一个简单的例子出发:

# 由s1:
X X X i
# 及s2:
Y Y Y Y Y j
## 是否可以交织得到s3:
Z Z Z Z Z Z Z Z Z Z

能交织形成s3的情况有两种:

  1. s3[i+j] = s1[i]并且dp[i-1][j]是可以交叠形成s3的前i+j-1个字符s3[:i+j-1]的;
  2. s3[i+j] = s2[j]并且dp[i][j-1]是可以交叠形成s3的前i+j-1个字符s3[:i+j-1]的。

如果s3[i+j]既不等于s1[i]又不等于s2[j],那肯定无法形成交织的s3。

再考虑base case,如果s1[:i]和s3[:i]能完全对应上,则dp[i][0]为True,这里完全对应上可以写成条件dp[i-1][0] == True && s1[i] == s3[i],对于s2也是同理。

代码:

class Solution:
def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
n,m = len(s1), len(s2)
if m+n != len(s3):
return False
dp = [[False for i in range(m+1)] for j in range(n+1)]
dp[0][0] = True
s1 = '#' + s1
s2 = '#' + s2
s3 = '#' + s3
for i in range(1, n+1):
if s1[i] == s3[i] and dp[i-1][0] == True:
dp[i][0] = True
for i in range(1, m+1):
if s2[i] == s3[i] and dp[0][i-1] == True:
dp[0][i] = True
for i in range(1, n+1):
for j in range(1, m+1):
if s1[i] == s3[j+i] and dp[i-1][j] == True:
dp[i][j] = True
elif s2[j] == s3[j+i] and dp[i][j-1] == True:
dp[i][j] = True
return dp[n][m]

2338. Count the Number of Ideal Arrays

题目:2338. Count the Number of Ideal Arrays,第301次周赛的最后一题,一道不那么直观的dp。给定n和maxValue,求出长度为n的,元素个数最大为maxValue的ideal array的个数。ideal array的定义为后一个元素可以整除前一个元素,且每一个元素的值域范围在[1, maxValue]。

解法:这题上来要注意到maxValue最大为10000,如果array中全是不同的元素且第一个元素为最小的1,最多能有14个不同的元素(2^13 < 10000 & 2^14>10000)。当我们考虑用多少个不同元素来形成array的时候,问题的复杂度简化为O(14*maxValue),定义dp[i][j]为元素最大值为i且一共有j个不同元素形成ideal array的个数。而原问题的个数可以由不同元素形成的个数组成,例如只有一个不同元素的array有maxValue个。那么对于最大为i,j个不同元素构成的长为n的array可以由dp[i][j]*C[n-1]j-1

代码:

class Solution:
def idealArrays(self, n: int, maxValue: int) -> int:
MOD = 1000_000_007
m = maxValue
dp = [[0 for i in range(15)] for j in range(maxValue+1)]
for j in range(1, maxValue+1):
dp[j][1] = 1
## 不同个数
for j in range(1, 14):
for i in range(1, maxValue+1):
k = 2
while k*i <= maxValue:
dp[k*i][j+1] = (dp[k*i][j+1]+dp[i][j])%MOD
k += 1
## 组合数
C = [[0 for i in range(15)] for j in range(n+1)]
for i in range(0, n):
for j in range(0,min(i+1,15)):
if j == 0:
C[i][j] = 1
else:
C[i][j] = (C[i-1][j-1] + C[i-1][j])%MOD
res = 0
for i in range(1, maxValue+1):
for j in range(1, min(n+1, 15)):
res = (res + dp[i][j]*C[n-1][j-1]) % MOD
return res