线性动态规划：最少硬币找零问题（Coin Change）

问题描述

给定不同面额的硬币和一个总金额。计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。
示例：
输入：coins = [1, 2, 5], amount = 11
输出：3
解释：11 = 5 + 5 + 1

解题过程

我们通过动态规划来解决，重点是定义dp数组以及状态转移方程。

步骤1：定义状态

我们定义 dp[i] 表示凑出金额 i 所需的最少硬币数量。
最终目标是求 dp[amount]。

步骤2：初始化

dp[0] = 0，因为凑出金额0不需要任何硬币。
对于其他 i（1 到 amount），我们初始化为一个很大的数（比如 amount+1 或 INF），表示暂时无法凑出。
因为硬币最小面额为1，最多需要 amount 枚硬币，所以用 amount+1 作为“无穷大”。

步骤3：状态转移方程

对于每个金额 i（从 1 到 amount），我们尝试每一种硬币 coin：
如果 coin <= i，说明可以用这枚硬币，那么 dp[i] 可能等于 dp[i - coin] + 1。
所以状态转移方程为：
dp[i] = min{ dp[i], dp[i - coin] + 1 }，其中 coin 是每个硬币面额，且 coin <= i。

步骤4：计算顺序

外层循环枚举金额 i 从 1 到 amount。
内层循环枚举每个硬币，尝试更新 dp[i]。
这样确保在计算 dp[i] 时，所有更小的金额都已经计算过。

步骤5：最终结果

如果 dp[amount] 仍然为初始的大数，则说明无法凑出，返回 -1；否则返回 dp[amount]。

举例说明

以 coins = [1, 2, 5], amount = 11 为例：
初始化 dp[0]=0, dp[1..11]=12。
i=1: 可用硬币1 → dp[1] = min(dp[1], dp[0]+1)=1。
i=2: 硬币1 → dp[2]=min(12, dp[1]+1)=2；硬币2 → dp[2]=min(2, dp[0]+1)=1。
i=3: 硬币1→dp[3]=min(12, dp[2]+1)=2；硬币2→dp[3]=min(2, dp[1]+1)=2。
以此类推，最终 dp[11] 计算过程：

• 用5 → dp[11] = dp[6] + 1。而 dp[6] 可由 dp[5]+1 得到，dp[5] 可由 5 直接得到（1枚），所以 dp[6]=2（5+1），则 dp[11]=3。
• 用2 → dp[11] = dp[9] + 1，dp[9] 最小为 3（5+2+2），所以是4，比3大，不更新。
• 用1 → dp[11] = dp[10] + 1，dp[10] 最小为 2（5+5），所以是3，相同。
  所以最终结果为3。

复杂度分析

时间复杂度：O(amount * n)，n 是硬币种类数。
空间复杂度：O(amount)。

代码实现（Python）

def coinChange(coins, amount):
    dp = [amount + 1] * (amount + 1)
    dp[0] = 0
    for i in range(1, amount + 1):
        for coin in coins:
            if coin <= i:
                dp[i] = min(dp[i], dp[i - coin] + 1)
    return dp[amount] if dp[amount] <= amount else -1

这样就解决了最少硬币找零问题。