原题（来源Leetcode）
硬币。给定数量不限的硬币，币值为25分、10分、5分和1分，编写代码计算n分有几种表示法。(结果可能会很大，你需要将结果模上1000000007)
示例 1:
输入: n = 5
输出: 2
解释: 有两种方式可以凑成总金额:
5=5
5=1+1+1+1+1
示例 2:
输入: n = 10
输出: 4
解释: 有四种方式可以凑成总金额:
10=10
10=5+5
10=5+1+1+1+1+1
10=1+1+1+1+1+1+1+1+1+1
解法
思想
动态规划，不过需要注意排列组合去重
代码
常见错误是：
class Solution {
public int waysToChange(int n) {
int[] dp = new int[n + 1];
int[] coins = new int[]{1,5,10,25};
for(int i = 1; i <= n; i++) {
for(int coin: coins) {
if(i - coin < 0) break;
dp[i] = (dp[i] + dp[i - coin]) % 1000000007;
}
}
return dp[n];
}
}
然而却忽略了重复的情况，例如6可以由1+5组合来，也可以由5+1组合来。
正确的答案其实只是将内外循环换了个顺序，保证这些数字是按递增的方式组合的，就能做到去重。：
class Solution {
public int waysToChange(int n) {
int[] dp = new int[n + 1];
int[] coins = new int[]{1,5,10,25};
for(int coin : coins) {
for(int i = coin; i <= n; i++) {
dp[i] = (dp[i] + dp[i - coin]) % 1000000007;
}
}
return dp[n];
}
}
原创文章，作者：彭晨涛，如若转载，请注明出处：https://www.codetool.top/article/%e7%a8%8b%e5%ba%8f%e5%91%98%e9%9d%a2%e8%af%95%e9%87%91%e5%85%b808-11-%e7%a1%ac%e5%b8%81/
相关推荐
-
leetcode24-两两交换链表中的节点
原题 给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。 你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。 示例: 给定 1->2->3->...
-
leetcode160-相交链表
原题 编写一个程序，找到两个单链表相交的起始节点。 如下面的两个链表： 在节点 c1 开始相交。 示例 1： 输入： intersectVal = 8, listA = [4,1,...
-
leetcode706-设计哈希映射
原题 不使用任何内建的哈希表库设计一个哈希映射 具体地说，你的设计应该包含以下的功能 put(key, value)：向哈希映射中插入(键,值)的数值对。如果键对应的值已经存在，更...
-
leetcode429-N叉树的层序遍历
原题 给定一个 N 叉树，返回其节点值的层序遍历。 (即从左到右，逐层遍历)。 例如，给定一个 3叉树 : 返回其层序遍历: [ [1], [3,2,4], [5,6] ] 说明:...
-
程序员面试金典08.01-三步问题
原题（来源Leetcode） 三步问题。有个小孩正在上楼梯，楼梯有n阶台阶，小孩一次可以上1阶、2阶或3阶。实现一种方法，计算小孩有多少种上楼梯的方式。结果可能很大，你需要对结果模...
-
leetcode5-最长回文子串
原题 给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。 示例1: 输入： "babad" 输出： "bab" 注意： "aba" 也是一个有...
-
leetcode705-设计哈希集合
原题 不使用任何内建的哈希表库设计一个哈希集合 具体地说，你的设计应该包含以下的功能 add(value)：向哈希集合中插入一个值。 contains(value) ：返回哈希集合...
-
leetcode1071-字符串的最大公因子
原题 对于字符串 S 和 T，只有在 S = T + ... + T（T 与自身连接 1 次或多次）时，我们才认定 “T 能除尽 S”。 返回最长字符串 X，要求满足 X 能除尽 ...
-
剑指offer64-求1+2+…+n
原题（来源Leetcode） 求 1+2+...+n ，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。 示例1...
