盛日辉的博客
0%

蓝桥-2022

发表于 分类于 ，

问题

https://www.lanqiao.cn/problems/2186/learning/

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
n = 2022
m = 10
# dp[i][j][k] 从1到i之间取j个数和为k的方案数
dp = [[[0] * (n + 1) for i in range(m + 1)] for j in range(n + 1)]

# 初始状态：从前i个数中取0个数和为0，方案数是1
for i in range(0, n + 1):
    dp[i][0][0] = 1

for i in range(1, n + 1):
    for j in range(1, m + 1):
        for k in range(1, n + 1):
            if i > k:
                dp[i][j][k] = dp[i - 1][j][k]
            else:
                dp[i][j][k] = dp[i - 1][j - 1][k - i] + dp[i - 1][j][k]
print(dp[n][m][n])

将题目转为0/1背包问题：

容量2022的包，编号1到2022的物体大小就是编号，取10个使得刚好装满的方案数。

我不好理解的是初始状态的设定。

滚动数组的做法：

1
2
3
4
5
6
7
8
9
10
11
12
13
n = 2022
m = 10
# dp[i][j][k] 从1到i之间取j个数和为k的方案数
dp = [[0] * (n + 1) for i in range(m + 1)]

# 初始状态：从取0个数和为0，方案数是1
dp[0][0] = 1

for i in range(1, n + 1):
    for j in range(m, 0, -1):
        for k in range(i, n + 1):
            dp[j][k] += dp[j - 1][k - i]
print(dp[m][n])

注意j的方向是从大到小，因为dp[j][k] 需要用到原来dp[j-1]][k-i]的数据。

dp[j][k] += dp[j - 1][k - i]状态转移方程的意思是第i个数不取（j个数的和是k``dp[j][k]）加上第i个数取（这时候取j-1个数的和是k-i）。

第i次循环就是取从1到第i个数。从1开始。

初始状态是0个数和为0的情况。