`找零（付款）问题c++动态规划 代码实现

下面是一份用动态规划解决找零（付款）问题的C++代码实现，希望对您有所帮助。

#include <iostream>
#include <vector>

using namespace std;

vector<int> coins = {1, 5, 10, 25}; // 硬币面额
const int INF = 0x3f3f3f3f; // 无穷大

int solve(int n) {
    vector<int> dp(n+1, INF); // 初始化动态规划数组
    dp[0] = 0; // 边界条件
    for (int i = 1; i <= n; i++) { // 枚举金额
        for (int j = 0; j < coins.size(); j++) { // 枚举硬币面额
            if (i - coins[j] >= 0) { // 如果当前金额可以使用这个硬币
                dp[i] = min(dp[i], dp[i-coins[j]] + 1); // 转移方程
            }
        }
    }
    return dp[n]; // 返回最小硬币数
}

int main() {
    int n;
    cin >> n;
    cout << solve(n) << endl;
    return 0;
}

在以上代码中，我们定义了一个 `coins` 数组存储硬币面额，然后使用动态规划解决找零问题。具体来说，我们定义了一个大小为 `n+1` 的动态规划数组 `dp`，其中 `dp[i]` 表示金额为 `i` 时需要的最小硬币数。然后我们从金额为 1 开始遍历到金额为 `n`，对于每个金额，再枚举硬币面额，如果当前金额可以使用这个硬币，则可以转移方程 `dp[i] = min(dp[i], dp[i-coins[j]] + 1)`，其中 `coins[j]` 表示第 `j` 个硬币的面额。最终，`dp[n]` 就是金额为 `n` 时需要的最小硬币数。

以上是一份简单的动态规划解决找零问题的C++代码实现，希望能够帮助到您。