本文主要是介绍代码随想录算法训练营第四十四天| 完全背包、518.零钱兑换 II、377.组合总和IV，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
代码随想录算法训练营第四十四天| 完全背包、518.零钱兑换 II、377.组合总和IV
题目
https://www.acwing.com/problem/content/3/
if __name__ == '__main__':a, b = input().split(' ')a, b = int(a), int(b)v, w = [0] * a, [0] * afor i in range(a):v[i], w[i] = input().split(' ')v[i], w[i] = int(v[i]), int(w[i])dp = [0] * (b + 1)for i in range(a):for j in range(v[i], b + 1):dp[j] = max(dp[j], dp[j - v[i]] + w[i])print(dp[b])
题目
518.零钱兑换 II
给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。
请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。
假设每一种面额的硬币有无限个。
题目数据保证结果符合 32 位带符号整数。
class Solution:def change(self, amount: int, coins: List[int]) -> int:dp = [0] * (amount + 1)dp[0] = 1for coin in coins:for j in range(coin, amount + 1):dp[j] += dp[j - coin]return dp[amount]
题目
377.组合总和IV
给你一个由 不同 整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。
题目数据保证答案符合 32 位整数范围。
class Solution:def combinationSum4(self, nums: List[int], target: int) -> int:dp = [0] * (target + 1)dp[0] = 1for j in range(1, target + 1):for i in range(len(nums)):if j >= nums[i]:dp[j] += dp[j - nums[i]]return dp[target]
这篇关于代码随想录算法训练营第四十四天| 完全背包、518.零钱兑换 II、377.组合总和IV的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
