代码随想录算法训练营第四十四天| 完全背包、518.零钱兑换 II、377.组合总和IV

本文主要是介绍代码随想录算法训练营第四十四天| 完全背包、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的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---