力扣面试题08.11：如何计算硬币组合数

一、问题理解

我们需要计算用1分、5分、10分和25分硬币组成n分的所有可能方式数。这是一个典型的完全背包问题。

二、算法选择

1. ‌动态规划‌：适合解决这种组合计数问题

2. ‌完全背包‌：每种硬币可以使用无限次

3. ‌有序处理‌：按硬币面值从小到大处理避免重复计数

三、关键实现细节

1. ‌初始化‌：dp[0]=1表示0分有1种表示法

2. ‌状态转移‌：dp[i] += dp[i-coin]

3. ‌取模运算‌：防止整数溢出

四、代码实现

class Solution {
public:
    int waysToChange(int n) {
        const int MOD = 1000000007;
        vector<int> dp(n + 1, 0);
        dp[0] = 1; // 初始化：0分有1种表示法（什么都不选）
       
        // 硬币面值按顺序处理
        int coins[4] = {1, 5, 10, 25};
       
        for (int coin : coins) {
            for (int i = coin; i <= n; ++i) {
                dp[i] = (dp[i] + dp[i - coin]) % MOD;
            }
        }
       
        return dp[n];
    }
};

五、优化思路

1. 可以优化空间复杂度到O(1)

2. 数学方法可以进一步优化