b站硬币可以换钱吗怎么兑换钱？

来源：蜘蛛抓取(WebSpider) 时间：2024-04-01 11:15 标签： b站硬币可以换钱吗
一、题目给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。你可以认为每种硬币的数量是无限的。什么意思？比如给一个总金额11块钱，硬币有三种：[1,2,5]，要求使用最少数量的硬币凑齐11块钱。这道题有点像左程云讲过的8类型袋子和6类型袋子装苹果的问题，但那道题是有数学规律的，因为8和6是确定的。本题则随机给硬币面额，要求最少数量。贪心会超时！使用动态规划，但不要被动态规划的套路把思路定死。二、动态规划分析设定dp[i] 的值为总金额为i时，需要的最少硬币个数。怎么获得转移方程呢？以amount==11，coins[1,2,5]为例，总金额11可以由dp[10] + 1、dp[9] + 1、dp[6] + 1得来，假设用1的硬币，那么就需要先凑齐10块钱，该方案下的dp[11] = dp[10] + 1；假设用2的硬币，那么需要先凑齐9块钱，该方案下的dp[11] = dp[9] + 1；同理，用5的硬币，dp[11] = dp[6] + 1。所以，取他们的最小值即可，dp[i]也起到缓存的作用三、代码class Solution{
public int coinChange(int[]

我要回帖

更多关于 b站硬币可以换钱吗 的文章

 

随机推荐