带恰好使用M枚硬币条件的Coin Change问题求解

现有面额为10、30、50的硬币，需使用恰好M枚硬币凑出指定金额sum。目前有一段参考代码，仅能计算凑出sum的所有可行方式，未满足恰好使用M枚硬币的条件。代码如下：

static long countWays(int coins[], int n, int sum)
{
    // Time complexity of this function: O(n*sum)
    // Space Complexity of this function: O(sum)

    // table[i] will be storing the number of solutions
    // for value i. We need sum+1 rows as the table is
    // constructed in bottom up manner using the base
    // case (sum = 0)
    long[] table = new long[sum + 1];

    // Initialize all table values as 0
    Arrays.fill(table, 0);

    // Base case (If given value is 0)
    table[0] = 1;

    // Pick all coins one by one and update the table[]
    // values after the index greater than or equal to
    // the value of the picked coin
    for (int i = 0; i < n; i++)
        for (int j = coins[i]; j <= sum; j++)
            table[j] += table[j - coins[i]];

    return table[sum];
}

// Driver Function to test above function
public static void main(String args[])
{
    int coins[] = { 10, 30, 50 };
    int n = coins.length;
    int sum = 80;
    System.out.println(countWays(coins, n, sum));
}

示例：
M=4 且 sum=80
输出：2
解释：

• 情况1：10×2 + 30×2 = 80（恰好使用4枚硬币）
• 情况2：10×3 + 50×1 = 80（恰好使用4枚硬币）

约束条件：

• M最大为5000
• sum最大为250000

要满足「恰好使用M枚硬币」的约束，需要扩展动态规划的状态，同时跟踪硬币数量和目标金额。

核心思路 #

原代码的一维DP数组仅记录凑出指定金额的总方式数，现在我们需要维护硬币数量和金额的二维状态：

• 定义dp[i][j]为用恰好i枚硬币凑出金额j的方式数
• 初始状态：dp[0][0] = 1（0枚硬币凑0元，仅1种方式），其余状态初始为0
• 状态转移：对于每种硬币面额coin，遍历硬币数量从1到M，金额从coin到sum，更新dp[i][j] += dp[i-1][j - coin]（即在i-1枚硬币凑出j-coin的基础上，添加1枚coin面额的硬币）

二维DP实现（清晰版） #

import java.util.Arrays;

public class ExactCoinCounter {
    static long countExactWays(int[] coins, int sum, int exactCoinCount) {
        // dp[i][j] = 用恰好i枚硬币凑出金额j的方式数
        long[][] dp = new long[exactCoinCount + 1][sum + 1];
        
        // 初始状态：0枚硬币凑0元
        dp[0][0] = 1;
        
        // 遍历每种硬币
        for (int coin : coins) {
            // 遍历硬币数量（从1到指定数量）
            for (int i = 1; i <= exactCoinCount; i++) {
                // 遍历金额，从当前硬币面额开始
                for (int j = coin; j <= sum; j++) {
                    dp[i][j] += dp[i - 1][j - coin];
                }
            }
        }
        
        return dp[exactCoinCount][sum];
    }

    public static void main(String[] args) {
        int[] coins = {10, 30, 50};
        int targetSum = 80;
        int targetCoinCount = 4;
        System.out.println(countExactWays(coins, targetSum, targetCoinCount)); // 输出2
    }
}

空间优化版（一维滚动数组） #

考虑到M和sum的上限，二维数组会占用较大内存，我们可以用两个一维数组交替更新，将空间复杂度从O(M*sum)降至O(sum)：

import java.util.Arrays;

public class ExactCoinCounterOptimized {
    static long countExactWays(int[] coins, int sum, int exactCoinCount) {
        // prev数组记录上一轮（i-1枚硬币）的状态
        long[] prev = new long[sum + 1];
        prev[0] = 1; // 初始状态：0枚硬币凑0元
        
        for (int k = 1; k <= exactCoinCount; k++) {
            long[] curr = new long[sum + 1];
            for (int coin : coins) {
                for (int j = coin; j <= sum; j++) {
                    curr[j] += prev[j - coin];
                }
            }
            prev = curr;
        }
        
        return prev[sum];
    }

    public static void main(String[] args) {
        int[] coins = {10, 30, 50};
        int targetSum = 80;
        int targetCoinCount = 4;
        System.out.println(countExactWays(coins, targetSum, targetCoinCount)); // 输出2
    }
}

复杂度说明 #

• 时间复杂度：O(n*M*sum)，其中n为硬币种类数，M为硬币数量上限，sum为金额上限。针对给定约束（n=3，M=5000，sum=250000），该复杂度可接受。
• 空间复杂度：二维版本为O(M*sum)，优化版本为O(sum)。

内容的提问来源于Stack Exchange，提问作者Learner