【LeetCode程序员面试金典】面试题 08.11. Coin LCCI

韩旭051

发布于 2020-06-22 12:09:15

51300

代码可运行

文章被收录于专栏：刷题笔记刷题笔记

运行总次数：0

代码可运行

Given an infinite number of quarters (25 cents), dimes (10 cents), nickels (5 cents), and pennies (1 cent), write code to calculate the number of ways of representing n cents. (The result may be large, so you should return it modulo 1000000007)

Example1:

Input: n = 5 Output: 2 Explanation: There are two ways: 5=5 5=1+1+1+1+1 Example2:

Input: n = 10 Output: 4 Explanation: There are four ways: 10=10 10=5+5 10=5+1+1+1+1+1 10=1+1+1+1+1+1+1+1+1+1 Notes:

You can assume:

0 <= n <= 1000000

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/coin-lcci 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。、

数学思想等差数列 C++

class Solution {
private:
    static constexpr int mod = 1000000007;

public:
    int waysToChange(int n) {
        int ans = 0;
        for (int i = 0; i * 25 <= n; ++i) {
            int rest = n - i * 25;
            int a = rest / 10;
            int b = rest % 10 / 5;
            ans = (ans + (long long)(a + 1) * (a + b + 1) % mod) % mod;
        }
        return ans;
    }
};

动态规划状态转移

class Solution {
private:
    static constexpr int mod = 1000000007;
    static constexpr int coins[4] = {25, 10, 5, 1};

public:
    int waysToChange(int n) {
        vector<int> f(n + 1);
        f[0] = 1;
        for (int c = 0; c < 4; ++c) {
            int coin = coins[c];
            for (int i = coin; i <= n; ++i) {
                f[i] = (f[i] + f[i - coin]) % mod;
            }
        }
        return f[n];
    }
};

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2020/05/22 ，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

编程算法

登录后参与评论

0 条评论

热度