解锁最优解，币种动态规划的魅力与应用

摘要：

在计算机科学和数学领域,动态规划（DynamicProgramming,DP）是一种强大的算法思想，它通过将复杂问题分解为更小的子问题，并存储子问题的解以避免重复计算，从而高效地解决优化问题，而在...

欧意交易所
全球三大交易所之一，注册领50 USDT数币盲盒！
注册链接 APP下载

在计算机科学和数学领域,动态规划（Dynamic Programming, DP）是一种强大的算法思想，它通过将复杂问题分解为更小的子问题，并存储子问题的解以避免重复计算，从而高效地解决优化问题，而在众多应用场景中，“币种动态规划”无疑是一个既经典又贴近生活的例子，它主要解决的是找零问题——即给定不同面额的硬币和一个总金额，求出凑成该金额所需的最少硬币数量，或者在特定条件下计算凑成该金额的所有可能组合方式。

什么是币种动态规划？

币种动态规划,顾名思义，是动态规划算法在货币兑换问题中的应用，其核心在于利用动态规划的最优子结构和重叠子问题特性。

• 问题定义：假设我们有 n 种面额为 c1, c2, ..., cn 的硬币，每种硬币的数量无限（或有限，取决于问题变种），给定一个总金额 amount，求凑成 amount 所需的最少硬币数量，或者有多少种不同的凑法。
• 核心思想：对于金额 i，其最优解（最少硬币数或组合数）可以基于比它小的金额 j（j < i）的最优解来构建，要凑金额 i，我们可以考虑使用某一枚硬币 c，那么问题就转化为凑金额 i - c 的最优解，再加上这枚硬币 c。

经典应用：最少硬币找零问题

这是币种动态规划最常见的形式,目标是找到凑成给定金额所需的最少硬币数量。

动态规划状态定义

我们可以定义一个一维数组 dp，dp[i] 表示凑成金额 i 所需的最少硬币数量。

状态初始化

• dp[0] = 0：凑成金额 0 所需的硬币数量为 0。
• 对于 i > 0，初始化 dp[i] 为一个较大的值（amount + 1 或无穷大），表示初始时该金额无法凑成或尚未计算。

状态转移方程

对于每个金额 i 从 1 到 amount，遍历每种硬币面额 c：

• c <= i（即硬币面额不超过当前金额），则我们可以考虑使用这枚硬币。 dp[i] = min(dp[i], dp[i - c] + 1) 这里，dp[i - c] + 1 表示使用一枚面额为 c 的硬币，加上凑成 i - c 金额所需的最少硬币数，我们取所有可能硬币 c 中的最小值。

最终结果

dp[amount] 即为凑成总金额 amount 所需的最少硬币数量。dp[amount] 仍然是初始时设定的大值，则表示无法凑成该金额。

示例： 假设硬币面额为 [1, 2, 5]，总金额 amount = 11。 初始化 dp = [0, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12]（amount + 1 = 12）

• i = 1:
  • c = 1: dp[1] = min(12, dp[0] + 1) = min(12, 1) = 1
  • c = 2, 5: 跳过
  • dp = [0, 1, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12]
• i = 2:
  • c = 1: dp[2] = min(12, dp[1] + 1) = min(12, 2) = 2
  • c = 2: dp[2] = min(2, dp[0] + 1) = min(2, 1) = 1
  • c = 5: 跳过
  • dp = [0, 1, 1, 12, 12, 12, 12, 12, 12, 12, 12, 12]
• i = 3:
  • c = 1: dp[3] = min(12, dp[2] + 1) = min(12, 2) = 2
  • c = 2: dp[3] = min(2, dp[1] + 1) = min(2, 2) = 2
  • c = 5: 跳过
  • dp = [0, 1, 1, 2, 12, 12, 12, 12, 12, 12, 12, 12]
• ... 以此类推，直到 i = 11
• dp[11] = 3（硬币组合 5 + 5 + 1 或 5 + 2 + 2 + 2 等，最少3枚）

变种：凑成金额的组合数

除了求最少硬币数,币种动态规划还可以用来计算凑成给定金额的不同组合方式。

状态定义

dp[i] 表示凑成金额 i 的不同硬币组合的数量。

状态初始化

• dp[0] = 1：凑成金额 0 有一种方式，即不使用任何硬币。
• dp[i > 0] = 0：初始时其他金额组合数为 0。

状态转移方程

这里有两种常见的思路,对应不同的组合定义（顺序是否视为不同）：

• 思路一（组合不考虑顺序）：先遍历硬币，再遍历金额。 对于每种硬币 c，从金额 c 到 amount： dp[i] += dp[i - c] 这种方式确保了组合的顺序不重要，1+2 和 2+1 被视为同一种组合。

• 思路二（组合考虑顺序）：先遍历金额，再遍历硬币。 对于每个金额 i，遍历每种硬币 c： c <= i，则 dp[i] += dp[i - c] 这种方式会考虑顺序，1+2 和 2+1 被视为两种不同的组合。

示例（思路一，不考虑顺序）： 硬币面额 [1, 2, 5]，amount = 5。 初始化 dp = [1, 0, 0, 0, 0, 0]

• 遍历硬币 c = 1:
  • i = 1: dp[1] += dp[0] => dp[1] = 1
  • i = 2: dp[2] += dp[1] => dp[2] = 1
  • i = 3: dp[3] += dp[2] => dp[3] = 1
  • i = 4: dp[4] += dp[3] => dp[4] = 1
  • i = 5: dp[5] += dp[4] => dp[5] = 1
• 遍历硬币 c = 2:
  • i = 2: dp[2] += dp[0] => dp[2] = 1 + 1 = 2 (1+1, 2)
  • i = 3: dp[3] += dp[1] => dp[3] = 1 + 1 = 2 (1+1+1, 1+2)
  • i = 4: dp[4] += dp[2] => dp[4] = 1 + 2 = 3 (1+1+1+1, 1+1+2, 2+2)
  • i = 5: dp[5] += dp[3] => dp[5] = 1 + 2 = 3 (1+1+1+1+1, 1+1+1+2, 1+2+2)
• 遍历硬币 c = 5:
  • i = 5: dp[5] += dp[0] => dp[5] = 3 + 1 = 4 (加上 5)
• `dp[

币安交易所
币安交易所是国际领先的数字货币交易平台，低手续费与BNB空投福利不断！
注册链接 APP下载