硬币

难度:

标签:

题目描述

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

代码结果

运行时间: 41 ms, 内存: 15.9 MB

/*
 * Problem: Given unlimited coins with values 25, 10, 5, and 1 cents, write code to calculate the number of ways to represent n cents.
 * The result can be very large, so you need to return the result modulo 1000000007.
 *
 * Approach using Java Streams:
 * This solution uses a similar dynamic programming approach as the previous one, but leverages Java Streams for more concise code.
 */

import java.util.stream.IntStream;

public class CoinChangeStream {
    public static int countWays(int n) {
        int MOD = 1000000007;
        int[] coins = {25, 10, 5, 1};
        int[] dp = new int[n + 1];
        dp[0] = 1;

        for (int coin : coins) {
            dp = IntStream.range(coin, n + 1).boxed()
                .mapToInt(i -> (dp[i] + dp[i - coin]) % MOD)
                .toArray();
        }

        return dp[n];
    }

    public static void main(String[] args) {
        System.out.println(countWays(5));  // Output: 2
        System.out.println(countWays(10)); // Output: 4
    }
}

解释

方法:

此题解采用动态规划类似的方法，但优化了空间复杂度。首先，考虑最大的硬币25分，从0枚到最多可能的枚数遍历，每次减去25分硬币占的总额后，计算剩余金额可以由10分和5分硬币组合的方式。这里利用了组合数学中的简单排列组合原理，即固定某些硬币后，其余硬币的组合方式数量。对于每个i（25分硬币的数量），计算剩余金额可以由10分硬币最多可以有多少枚（a），以及5分硬币最多可以有多少枚（b）。然后用组合方式计算这些硬币可以组合成剩余金额的方法数。最后，所有可能的i的总和即为答案。

时间复杂度:

O(n/25) 或简化为 O(n)

空间复杂度:

O(1)

代码细节讲解

🦆

题解中提到了`计算剩余金额可以由10分和5分硬币组合的方式`，请问这种组合方式是如何确保覆盖所有可能的硬币组合？

▷

题解中的组合方式通过固定25分硬币的数量，然后计算剩余金额如何由10分和5分硬币组成。通过遍历每个可能的25分硬币数量，我们可以确保处理所有可能的组合情况。对于每个固定的25分硬币数量，我们计算剩余金额（rest）。然后确定该金额最多可以由多少个10分硬币（a）和余数中最多可以由多少个5分硬币（b）组成。通过这种方式，我们实际上是在对每种可能的25分硬币数量，探索所有可能的10分和5分硬币的组合，确保没有遗漏任何一种可能的硬币组合方式。

🦆

在动态规划的优化过程中，为何选择只使用常数个变量而不使用数组来维护状态？这种方式有什么优缺点？

▷

在动态规划的优化过程中，选择使用常数个变量而不使用数组来维护状态是为了减少空间复杂度。当使用数组时，我们可能需要为每一种金额值维护一个状态值，这会导致空间复杂度为O(n)。使用常数个变量可以将空间复杂度降低到O(1)，这对于处理大量数据或在内存限制较严的情况下非常有利。缺点是这种优化通常使得代码的逻辑复杂度增加，可能更难理解和维护。

🦆

题解中的`ans += (a + 1) * (a + b + 1)`计算方式是基于什么组合数学的原理？能否具体解释其正确性？

▷

题解中的计算方式`ans += (a + 1) * (a + b + 1)`基于的是组合数学中的分配原理。这里的`(a + 1)`代表选择0到a个10分硬币的所有可能情况，`(a + b + 1)`则进一步代表在已经选定了10分硬币的基础上，再选择0到a+b个5分硬币的所有情况（因为剩余金额可以完全由5分硬币填满）。这样的计算方式实际上是在计算所有可能的10分硬币和5分硬币的组合数，确保覆盖了所有可能的硬币组合。这种计算是正确的，因为它考虑了所有分割剩余金额的方式，无论剩余是多少。

硬币

题目描述

代码结果

解释

代码细节讲解

相关问题