难度: Medium
硬币。给定数量不限的硬币，币值为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
说明：
注意:
你可以假设：
运行时间: 41 ms
内存: 15.9 MB
class Solution:
def waysToChange(self, n: int) -> int:
ans = 0
for i in range(n // 25 + 1):
rest = n - i * 25
a, b = rest // 10, rest % 10 // 5
ans += (a + 1) * (a + b + 1)
return ans % 1000000007
# mod = 10**9 + 7
# coins = [25, 10, 5, 1]
# f = [1] + [0] * n
# for coin in coins:
# for i in range(coin, n + 1):
# f[i] += f[i - coin]
# return f[n] % mod
此题解采用动态规划类似的方法，但优化了空间复杂度。首先，考虑最大的硬币25分，从0枚到最多可能的枚数遍历，每次减去25分硬币占的总额后，计算剩余金额可以由10分和5分硬币组合的方式。这里利用了组合数学中的简单排列组合原理，即固定某些硬币后，其余硬币的组合方式数量。对于每个i（25分硬币的数量），计算剩余金额可以由10分硬币最多可以有多少枚（a），以及5分硬币最多可以有多少枚（b）。然后用组合方式计算这些硬币可以组合成剩余金额的方法数。最后，所有可能的i的总和即为答案。
时间复杂度: O(n/25) 或简化为 O(n)
空间复杂度: O(1)
class Solution:
def waysToChange(self, n: int) -> int:
ans = 0
for i in range(n // 25 + 1): # 遍历每种可能的25分硬币的数量
rest = n - i * 25 # 计算去掉25分硬币后剩余的金额
a, b = rest // 10, rest % 10 // 5 # 计算剩余金额中10分和5分硬币的最大可能数量
ans += (a + 1) * (a + b + 1) # 计算当前25分硬币数量下的总组合数
return ans % 1000000007 # 返回结果，同时取模防止数字过大
题解中的组合方式通过固定25分硬币的数量，然后计算剩余金额如何由10分和5分硬币组成。通过遍历每个可能的25分硬币数量，我们可以确保处理所有可能的组合情况。对于每个固定的25分硬币数量，我们计算剩余金额（rest）。然后确定该金额最多可以由多少个10分硬币（a）和余数中最多可以由多少个5分硬币（b）组成。通过这种方式，我们实际上是在对每种可能的25分硬币数量，探索所有可能的10分和5分硬币的组合，确保没有遗漏任何一种可能的硬币组合方式。
在动态规划的优化过程中，选择使用常数个变量而不使用数组来维护状态是为了减少空间复杂度。当使用数组时，我们可能需要为每一种金额值维护一个状态值，这会导致空间复杂度为O(n)。使用常数个变量可以将空间复杂度降低到O(1)，这对于处理大量数据或在内存限制较严的情况下非常有利。缺点是这种优化通常使得代码的逻辑复杂度增加，可能更难理解和维护。
题解中的计算方式`ans += (a + 1) * (a + b + 1)`基于的是组合数学中的分配原理。这里的`(a + 1)`代表选择0到a个10分硬币的所有可能情况，`(a + b + 1)`则进一步代表在已经选定了10分硬币的基础上，再选择0到a+b个5分硬币的所有情况（因为剩余金额可以完全由5分硬币填满）。这样的计算方式实际上是在计算所有可能的10分硬币和5分硬币的组合数，确保覆盖了所有可能的硬币组合。这种计算是正确的，因为它考虑了所有分割剩余金额的方式，无论剩余是多少。