UVA 10626 Buying Coke：記憶化 DFS 最小投幣數

題目大意

購買 C 瓶可樂，每瓶 8 分。擁有 1 分、5 分、10 分硬幣若干。每次投幣購買一瓶，找零規則：多投金額自動找零（優先找大面額？題目隱含找零最優）。求最小總投幣次數。

狀態與轉移

狀態 (c, n1, n5, n10)：剩餘 c 瓶，手中 1/5/10 分硬幣數。
目標：dfs(c, n1, n5, n10) 返回最小投幣數。
每次購買有以下可行支付方案（經分析最優）：

1. 10 分 → 找 3 個 1 分：投 1 枚，n10-1, n1+3
2. 10 分 + 3×1 分 → 找 1 個 5 分：投 4 枚，n10-1, n1-3, n5+1
3. 5 分 + 3×1 分：投 4 枚，n5-1, n1-3
4. 2×5 分 → 找 2×1 分：投 2 枚，n5-2, n1+2
5. 8×1 分：投 8 枚，n1-8

其他方案（如 10 分單投找 2 分）均不優於上述組合。

代碼實現

#include <cstdio>
#include <cstring>
#include <climits>
#include <algorithm>
using namespace std;

const int INF = 0x3f3f3f3f;
int dp[155][55][155]; // [n1][n5][n10] -> min coins, n1≤150, n5≤50, n10≤150

int dfs(int c, int n1, int n5, int n10) {
    if (c == 0) return 0;
    int &res = dp[n1][n5][n10];
    if (res != -1) return res;
    res = INF;
    if (n10 >= 1) res = min(res, dfs(c-1, n1+2, n5, n10-1) + 1);       // 10 -> 找3个1
    if (n5 >= 2)  res = min(res, dfs(c-1, n1+2, n5-2, n10) + 2);       // 2*5 -> 找2个1
    if (n1 >= 8)  res = min(res, dfs(c-1, n1-8, n5, n10) + 8);         // 8*1
    if (n1 >= 3 && n10 >= 1) res = min(res, dfs(c-1, n1-3, n5+1, n10-1) + 4); // 10+3*1 -> 找5
    if (n1 >= 3 && n5 >= 1)  res = min(res, dfs(c-1, n1-3, n5-1, n10) + 4);   // 5+3*1
    return res;
}

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        int C, n1, n5, n10;
        scanf("%d%d%d%d", &C, &n1, &n5, &n10);
        memset(dp, -1, sizeof(dp));
        printf("%d\n", dfs(C, n1, n5, n10));
    }
    return 0;
}

複雜度分析

• 狀態數：C ≤ 150, n1 ≤ 150, n5 ≤ 50, n10 ≤ 150，但實際可達狀態遠小於理論上限，記憶化搜索極快。
• 每狀態轉移 O(1)，總時間約 O(可達狀態數)。

關鍵優化

• 僅枚舉 5 種最優支付方式，大幅減少分支。
• 硬幣數上界可由初始值與最大找零推導，陣列開 [155][55][155] 足夠。
• 遞歸深度 ≤ C，無棧溢出風險。

此題展示了如何將硬幣找零問題轉化為狀態空間搜索，並通過領域知識剪枝支付方案。