【高级技巧】动态规划：最少金币的子问题分解

底层原理

求"凑出目标值的最少金币枚数"（面额 1、5、11）：贪心会错——凑 15 贪心拿 11 加四枚 1 共 5 枚，最优是三枚 5。动态规划把大问题拆成子问题：f(n) 等于 min(f(n-v)) + 1 对每种面额 v，f(0)=0 起步自底向上填表——每个状态只算一次，复杂度 O(目标值乘面额数)。它存的是"子问题的确定答案"，与蒙特卡洛的"采样逼近"分属两路：DP 给精确解，前提是最优子结构成立。

高级封装

最少枚数填表。示例代码如下：

local function minCoins(target, faces)
    local f = { [0] = 0 }
    for n = 1, target do
        local best = math.huge
        for _, v in ipairs(faces) do
            if n >= v and f[n - v] + 1 < best then
                best = f[n - v] + 1
            end
        end
        f[n] = best
    end
    return f[target]
end
print(minCoins(15, { 1, 5, 11 }))

输出 3（5+5+5）——贪心的 5 枚被填表法压到 3 枚，差距来自"局部最优不等于全局最优"。
礼包定价接线。示例代码如下：

local faces = { 1, 5, 20 }
print(minCoins(40, faces))

祖玛教主纪念礼包定价 40 金币、面额券 1/5/20：填表得 2 枚（20+20）——限时礼包上线前按此校验定价能否被小额券组合套利。

性能对比

无记忆的递归穷举求 f(40) 展开数十万次函数调用；自底向上填表只算 40 个状态、每状态扫 3 种面额即 120 次比较，微秒级。目标值 10000、面额 5 种时也只需 5 万次比较约 2 毫秒；空间 O(目标值)：10000 个状态约 400KB。

适用边界

三个不适用场景：一是有贪心正确性证明的面额体系（标准币制），贪心一次遍历更快；二是目标值到百万级，填表的内存与时间失控，改记忆化搜索按需计算；三是问题无最优子结构（选择之间互相纠缠不成子问题），DP 不适用，回到搜索或采样。