從暴力遞迴到動態規劃#

int getMinCountsHelper(int total, int[] values) {
    // 邊界條件：金額為 0，不需要硬幣
    if (total == 0) { return 0; }

    int minCount = Integer.MAX_VALUE;

    for (int i = 0; i < values.length; i++) {
        int currentValue = values[i];

        // 面值大於總額，跳過
        if (currentValue > total) { continue; }

        int rest = total - currentValue;
        int restCount = getMinCountsHelper(rest, values);

        // 組合不可行，跳過
        if (restCount == -1) { continue; }

        int totalCount = 1 + restCount;
        if (totalCount < minCount) {
            minCount = totalCount;
        }
    }

    return (minCount == Integer.MAX_VALUE) ? -1 : minCount;
}

int getMinCountsHelper(int total, int[] values, int[] memo) {
    // 查詢備忘錄
    int savedMinCount = memo[total];
    if (savedMinCount != -2) {
        return savedMinCount;
    }

    int minCount = Integer.MAX_VALUE;

    for (int i = 0; i < values.length; i++) {
        int currentValue = values[i];
        if (currentValue > total) { continue; }

        int rest = total - currentValue;
        int restCount = getMinCountsHelper(rest, values, memo);

        if (restCount == -1) { continue; }

        int totalCount = 1 + restCount;
        if (totalCount < minCount) {
            minCount = totalCount;
        }
    }

    // 存入備忘錄
    if (minCount == Integer.MAX_VALUE) {
        memo[total] = -1;
        return -1;
    }

    memo[total] = minCount;
    return minCount;
}

// 初始化備忘錄
int[] memo = new int[total + 1];
Arrays.fill(memo, -2);  // -2 表示未計算
memo[0] = 0;           // 金額 0 需要 0 枚硬幣

int getMinCounts(int k, int[] values) {
    int[] memo = new int[k + 1];
    Arrays.fill(memo, k + 1);  // 初始化為「無窮大」
    memo[0] = 0;               // 初始化狀態

    for (int i = 1; i <= k; i++) {          // 自底向上
        for (int coin : values) {            // 嘗試每種硬幣
            if (i - coin < 0) { continue; }
            memo[i] = Math.min(memo[i], memo[i - coin] + 1);  // 決策
        }
    }

    return (memo[k] == k + 1) ? -1 : memo[k];
}