「LeetCode每日一题」—— LCCI.08.11. 硬币
LCCI.08.11. 硬币
链接：https://leetcode-cn.com/problems/coin-lcci/
难度：中等
题目
点击原文链接跳转查看题目
思路
这题是完全背包问题，因为每种硬币的数量都是无限。
我们用动态规划来做，设dp[i][j]为遍历到当下这个硬币时，组成金额j的方法数目。
在后面我们有两种可能
1.当前硬币没有取，dp[i][j] = dp[i-1][j]
2.当前硬币取了，dp[i][j] = dp[i][j-coins[i[]]
状态转移方程：
dp[i][j]=dp[i-1][j]+dp[i][j-coins[i]]
上面的转移方程可以把第一个维度去掉，变成：
dp[j]=dp[j]+dp[j-coins[i]]
然后设置初始化条件dp[0]=1，代表0(没有硬币)也是一种情况。
代码见解决方案。
方案代码
解决方案：
class Solution:
def waysToChange(self, n: int) -> int:
coins = [1, 5, 10, 25]
dp = [0] * (n + 1)
dp[0] = 1
for coin in coins :
for i in range(coin, n + 1) :
dp[i] = dp[i] + dp[i - coin]
return dp[n] % 1000000007原创文章，作者：flypython，如若转载，请注明出处：http://flypython.com/algorithm/leetcode/348.html
微信扫一扫 
支付宝扫一扫 相关推荐
-
「LeetCode每日一题」——695. 岛屿的最大面积
695. 岛屿的最大面积 链接：https://leetcode-cn.com/problems/max-area-of-island/难度：中等 题目 给定一个包含了一些 0 和…
-
「LeetCode每日一题」—— 445. 两数相加 II
445. 两数相加 II 链接：https://leetcode-cn.com/problems/add-two-numbers-ii/难度：中等 题目 点击原文链接跳转查看题目 …
-
「LeetCode每日一题」—— 460. LFU缓存
460. LFU缓存 题目链接：https://leetcode-cn.com/problems/lfu-cache/难度：困难 题目 点击原文链接跳转查看题目 请你为 最不经常使…
-
「LeetCode每日一题」206. 反转链表
206. 反转链表 题目 反转一个单链表。 示例: 输入: 1->2->3->4->5->NULL输出: 5->4->3->2-&g…
-
「LeetCode每日一题」—— 200. 岛屿数量
200. 岛屿数量 链接：https://leetcode-cn.com/problems/number-of-islands/难度：中等 思路 这题比较简单，思路就是DFS。 我…
-
「LeetCode每日一题」—— 22. 括号生成
22. 括号生成 链接：https://leetcode-cn.com/problems/generate-parentheses/难度：中等 题目 数字 n 代表生成括…
-
「LeetCode每日一题」——121. 买卖股票的最佳时机
121. 买卖股票的最佳时机 链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/难度：简单 题…
-
「LeetCode每日一题」——994. 腐烂的橘子
994. 腐烂的橘子 链接：https://leetcode-cn.com/problems/rotting-oranges/难度：简单 题目 在给定的网格中，每个单元格可以有以下…
-
「LeetCode每日一题」—— 355. 设计推特
355. 设计推特 链接：https://leetcode-cn.com/problems/design-twitter/难度：中等 题目 点击原文链接跳转查看题目 思路 思路见代…
-
「LeetCode每日一题」—— LOCF.51. 数组中的逆序对
LOCF.51. 数组中的逆序对 链接：https://leetcode-cn.com/problems/shu-zu-zhong-de-ni-xu-dui-lcof/难度：中等 …
您必须登录才能发表评论。