题解 | #兑换零钱(一)#
兑换零钱(一)
https://www.nowcoder.com/practice/3911a20b3f8743058214ceaa099eeb45
dp=[],代表当总钱数为i时需要的最少钱币数；
假设当前硬币种类为{2,3,5}三种，那么dp[2]=1;dp[3]=1;dp[5]=dp[2]+dp[3];
以此类推的话，dp[6]=min(dp[2]+dp[4],dp[3]+dp[3]}),这时我们可以发现，所谓的球最少硬币数不过是：
令j为硬币集合的下标，i为总钱数；那么便是对j作循环，使得dp[i-j]+dp[j]的和最小（每一项都必须大于0），那么递推公式即为dp[i]=min(dp[i],dp[i-j]+dp[j]),对硬币种类循环完，就得到了当总钱数为i时所需要的最少硬币数。结果返回dp[-1]即可。
投递腾讯等公司8个岗位 >
网易互娱一面35人在聊
查看26道真题和解析