信奥赛CSP动态规划入门-最小硬币问题

针对**“最小硬币问题”**的详细分步解析与程序实现，通过将大问题分解为小问题的方式讲解动态规划的应用：

一、问题拆解步骤

1. 明确问题定义

大问题：用面值1元和5元的硬币凑出N元，最少需要多少枚硬币？
小问题：凑出k元（0 ≤ k ≤ N）所需的最小硬币数。

2. 状态定义

• 定义数组：dp[i] 表示凑出i元所需的最小硬币数
• 物理意义：每个dp[i]都是独立的小问题解

3. 初始条件

4. 状态转移方程

递推逻辑：
对每个金额i，尝试使用所有可能的硬币面值coin，取最小值：

dp[i] = min(dp[i], dp[i - coin] + 1)

二、分步程序实现

#include <iostream>
#include <algorithm>  // 使用min函数
using namespace std;

int main() {
    int coins[] = {1, 5};      // 硬币面值
    int target;                // 目标金额
    cout << "请输入目标金额：";
    cin >> target;

    // 步骤1：初始化dp数组
    int dp[100];               // 假设最大金额不超过99元
    fill(dp, dp + 100, 999);   // 初始化为极大值（代表不可达）
    dp[0] = 0;                 // 凑0元需要0个硬币

    // 步骤2：逐个解决小问题
    for (int i = 1; i <= target; i++) {  // 从1元开始计算
        // 尝试每一种硬币
        for (int coin : coins) {         // C++11范围循环
            if (i >= coin) {             // 确保不会出现负数
                // 状态转移：用更小问题的解构建当前解
                dp[i] = min(dp[i], dp[i - coin] + 1);
            }
        }
    }

    // 步骤3：输出最终解
    if (dp[target] != 999) {
        cout << "最少需要 " << dp[target] << " 枚硬币" << endl;
    } else {
        cout << "无法凑出目标金额！" << endl;
    }

    return 0;
}

三、动态规划过程演示（以target=10为例）

1. 初始化数组

2. 逐步填充过程

• i=1元：
  • 尝试1元硬币：dp[1] = min(∞, dp[0]+1) = 1
  • 5元硬币不可用
• i=5元：
  • 尝试1元硬币：dp[5] = min(∞, dp[4]+1) = ∞
  • 尝试5元硬币：dp[5] = min(∞, dp[0]+1) = 1
• i=10元：
  • 尝试1元硬币：dp[10] = dp[9]+1 = 2+1=3
  • 尝试5元硬币：dp[10] = dp[5]+1 = 1+1=2

3. 最终结果

四、关键点解析

1. 大问题化小问题：

   • 将"凑10元"分解为"凑1元、2元…9元"的子问题
   • 每个子问题的解都记录在dp[]数组中

2. 递推关系本质：

   凑i元的最优解 = min(
       凑(i-1元)的最优解 + 1个1元硬币,
       凑(i-5元)的最优解 + 1个5元硬币
   )
   

3. 时间复杂度：O(M×N)

   • M为硬币种类数，N为目标金额

五、测试样例

注意：测试时需确保硬币面值数组与实际题目一致