思想

动态规划 1 及之后的文章是实证，通过不同题目阐述 dp 思想如何应用。

实例

零钱兑换 leetcode 322
输入：
（1）coins: List[int]，一个整数组，硬币的面额列表；
（2）amount: int，目标额度，也就是要兑换的总金额；
输出：
int，用 coins 的面额列表中的值凑成目标额度 amount 所需的最小硬币数量，如果无法兑换则返回 -1。

假定硬币数量是无限的。

举例：
当 coins = [1,2,5], amount= 11 时，最少兑换硬币数量是 3 (5 + 5 + 1 = 11)

状态

这道题目有两个值，一个是面额，另一个是数量。最终要返回的是数量，不关心用什么样的面额组成，所以状态设置为数量。

dp 数组

这里的状态是数量，dp 数组要将数量和面额关联起来，也就是兑换某个面额所需的数量。下标表示面额，数组中的值表示数量。
在上例中，dp 数组长度应该是 12（因为用下标表示了面额，而下标从 0 开始，所以长度是面额 + 1）：
[0, 1, 1, 2, 2, 1, ...]

状态转移方程

整理 dp 数组的过程暗含了状态转移方程，从较小的面额向上计算需要的硬币数量，所需的硬币数量是当前面额之前 value 加上面额的数量最小值。
例如 dp[4] = min(dp[4-1] + 1, dp[4-2] + 1, dp[4-5] + 1) = 2
这里的 4 是当前面额，减去的 1,2,5 是面额列表，含义是之前 dp[x] 中的数量如果加上这样一个面额的硬币可以兑换当前面额，所以最后 +1，表示加上一个选定面额的兑换。

初始值

占位 index=0 的值设置为 0，表示面额 0 无需兑换。
当没有计算的时候全部设置为 -1，因为题目中无法兑换返回值是 -1。
当前面额等于硬币面额列表中的数字时，数量设置为 1。

编码

from typing import List

def coin_change(coins: List[int], amount: int) -> int:
    # 初始化
    dp_table = [0] + [-1] * amount
    # 状态转移方程逐个求解，注意边界，dp_table[0] 只是占位略过，dp_table[amount] 是终点
    for i in range(1, amount + 1):
        # 如果当前面额在面额列表中，数量设为 1，且是最小值，跳过后续判断
        if i in coins:
            dp_table[i] = 1
            continue
        # 逐个面额求解
        for coin in coins:
            if i - coin <= 0:
                continue
            # 之前面额无解放弃
            if dp_table[i - coin] == -1:
                continue
            if dp_table[i] == -1:
                dp_table[i] = dp_table[i - coin] + 1
            else:
                dp_table[i] = min(dp_table[i], dp_table[i - coin] + 1) 
    return dp_table[amount]

相关

动态规划 0