Leetcode: 面试题 08.11. 硬币

本文主要是介绍Leetcode: 面试题 08.11. 硬币，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

题目链接：https://leetcode-cn.com/problems/coin-lcci

硬币。给定数量不限的硬币，币值为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
说明：注意:你可以假设：0 <= n (总金额) <= 1000000

解题记录

• 4种情况，由于25和10都是5的倍数
• 任何数字都可以由1组成
• n%5部分只能是1，抛去不看了
• 在抛去25情况下，看剩下的值，只分5和10的情况，在循环10的个数的时候可以总结出规律

class Solution {public int waysToChange(int n) {int res = 0;for (int i = 0; i <= n / 25; ++i) {long tmp = (n - i * 25) / 10;res = (int)((res + (tmp + 1) * (n / 5 - i * 5 + 1 - tmp)) % 1000000007);}return res;}
}

这篇关于Leetcode: 面试题 08.11. 硬币的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---