线性动态规划：硬币找零问题（最少硬币数） 题目描述 给定不同面额的硬币数组 coins 和一个总金额 amount ，要求计算凑成总金额所需的最少硬币个数。如果无法凑出总金额，返回 -1 。假设每种硬币的数量无限。 示例 输入： coins = [1, 2, 5] , amount = 11 输出： 3 解释： 11 = 5 + 5 + 1 解题思路 问题分析 目标：用最少的硬币凑出金额 amount 。 约束：硬币面额固定且数量无限，可能无法凑出目标金额。 关键：存在重叠子问题（例如凑 amount-1 可能被多次计算），适合动态规划。 状态定义 设 dp[i] 表示凑出金额 i 所需的最少硬币数。 最终目标：求 dp[amount] 。 状态转移方程 对于每个金额 i ，遍历所有硬币面额 coin ： 若 i >= coin ，说明可以用 coin 面额硬币，剩余金额为 i-coin 。 若 dp[i-coin] 有解（即不是无穷大），则： \[ dp[ i] = \min(dp[ i], dp[ i-coin ] + 1) \] 初始化： dp[0] = 0 （金额0不需要硬币），其他 dp[i] 初始化为一个极大值（如 amount+1 ）。 边界情况 若 amount = 0 ，直接返回 0 。 若所有硬币面额均大于 amount ，则 dp[amount] 无解。 逐步计算过程 以 coins = [1, 2, 5] , amount = 11 为例： 初始化 dp = [0, ∞, ∞, ..., ∞] （长度为 12 ，索引 0 到 11 ）。 计算 dp[1] 遍历硬币： 硬币 1 ： 1 >= 1 ， dp[1] = min(∞, dp[0]+1) = 1 硬币 2 和 5 面额大于1，跳过。 结果： dp[1] = 1 。 计算 dp[2] 硬币 1 ： dp[2] = min(∞, dp[1]+1) = 2 硬币 2 ： dp[2] = min(2, dp[0]+1) = 1 结果： dp[2] = 1 。 继续计算更高金额 dp[3] ：用硬币 1 （ dp[2]+1=2 ）或 2 （ dp[1]+1=2 ），结果为 2 。 dp[4] ：用硬币 1 （ dp[3]+1=3 ）、 2 （ dp[2]+1=2 ），结果为 2 。 dp[5] ：用硬币 1 （ dp[4]+1=3 ）、 2 （ dp[3]+1=3 ）、 5 （ dp[0]+1=1 ），结果为 1 。 依此类推，最终 dp[11] = 3 （由 dp[6]+5 或 dp[9]+2 等推导）。 结果验证 dp[11] = 3 对应方案 5+5+1 ，与示例一致。 复杂度分析 时间复杂度：O(amount × n)，其中 n 为硬币种类数。 空间复杂度：O(amount)，用于存储 dp 数组。 核心要点 动态规划通过子问题递推，避免重复计算。 初始化 dp[0]=0 是基础，其他值初始化为无穷大以确保最小值比较有效。 若最终 dp[amount] 仍为初始极大值，说明无解，返回 -1 。