刷题刷出新高度，偷偷领先！偷偷领先！偷偷领先！ 关注我们，悄悄成为最优秀的自己！

简答题

植物大战僵尸

编程实现：

为了应对僵尸，需要选取多种不同的植物，现有n种植物可供选择，已知每种植物的攻击力，想要选取攻击力之和为k的植物，相同植物不能重复选择，有多少种不同的选择方案？

输入描述

第一行输入两个正整数n和k，中间用空格隔开，表示有n种植物可供选择（1≤n≤50），目标攻击力之和为k（1≤k≤100）。

第二行输入n个正整数，表示每种植物的攻击力（1≤攻击力≤100）。

输出描述

输出达到目标攻击力之和的选择方案的数量。


输入样例

3 10
5 2 3

输出样例

1

使用微信搜索喵呜刷题，轻松应对考试！

答案：

```pythondef count_ways(n, k, plants):dp = [[0] * (k + 1) for _ in range(n + 1)]for i in range(1, n + 1):for j in range(1, k + 1):for p in range(i):if plants[p - 1] <= j:dp[i][j] += dp[p - 1][j - plants[p - 1]]return dp[n][k]n, k = map(int, input().split())plants = list(map(int, input().split()))print(count_ways(n, k, plants))```

解析：

【喵呜刷题小喵解析】：
这个问题是一个经典的组合问题，可以使用动态规划来解决。我们定义一个二维数组dp，其中dp[i][j]表示选取i种植物，攻击力之和为j的方案数。

对于每一种植物，我们有两种选择：选或者不选。如果我们选择第i种植物，那么攻击力之和就会增加plants[i-1]，同时我们需要在前i-1种植物中选择一些植物，使得攻击力之和为j-plants[i-1]。因此，dp[i][j]就等于dp[p-1][j-plants[p-1]]的和，其中p的范围是从1到i。

具体的算法如下：

1. 初始化dp数组，dp[0][0]=1，表示不选任何植物也是一种方案。
2. 对于i从1到n，对于j从1到k，对于p从1到i，如果plants[p-1]<=j，那么dp[i][j] += dp[p-1][j-plants[p-1]]。
3. 最后返回dp[n][k]，即选取n种植物，攻击力之和为k的方案数。

以上代码实现了这个算法，首先读入n和k，然后读入每种植物的攻击力，最后输出方案数。
创作类型：
原创

本文链接：植物大战僵尸 编程实现： 为了应对僵尸，需要选取多种不同的植物，现有n种植物可供选择，已知每种植物的

版权声明：本站点所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明文章出处。

让学习像火箭一样快速，微信扫码，获取考试解析、体验刷题服务，开启你的学习加速器！

分享考题
share