解题思路

这是一个完全背包问题的变种，求组合数。关键点：

  1. 状态定义：

    • 表示组成金额 的方案数

  2. 状态转移：

    • 对每个面值 ，更新所有可能的金额

  3. 边界条件：

    • ，表示金额为 时有 种方案（什么都不选）
    • 金额为负数时方案数为

代码

class Exchange {
public:
    int countWays(vector<int>& changes, int n, int x) {
        vector<int> dp(x + 1, 0);
        dp[0] = 1;  // 初始化，金额为0时有1种方案
        
        // 遍历每种面值
        for(int coin : changes) {
            // 更新所有可能的金额
            for(int i = coin; i <= x; i++) {
                dp[i] += dp[i - coin];
            }
        }
        
        return dp[x];
    }
};

import java.util.*;

public class Exchange {
    public int countWays(int[] changes, int n, int x) {
        int[] dp = new int[x + 1];
        dp[0] = 1;  // 初始化，金额为0时有1种方案
        
        // 遍历每种面值
        for(int coin : changes) {
            // 更新所有可能的金额
            for(int i = coin; i <= x; i++) {
                dp[i] += dp[i - coin];
            }
        }
        
        return dp[x];
    }
}

# -*- coding:utf-8 -*-
class Exchange:
    def countWays(self, changes, n, x):
        dp = [0] * (x + 1)
        dp[0] = 1
        
        for coin in changes:
            for i in xrange(coin, x + 1):
                dp[i] += dp[i - coin]
        
        return dp[x]

算法及复杂度

  • 算法：动态规划（完全背包）
  • 时间复杂度：，其中 为零钱种类数， 为目标金额
  • 空间复杂度：，需要一个长度为x+1的dp数组