找零钱问题动态规划c++

你好！对于找零钱问题的动态规划解法，可以使用以下步骤：

1. 定义问题：我们需要找零钱的总金额是amount，可用的硬币面额数组是coins。

2. 初始化状态：创建一个长度为amount+1的数组dp，并将所有元素初始化为无穷大（表示不可达）。

3. 设置初始条件：将dp设为0，表示找零金额为0时，需要0枚硬币。

4. 进行状态转移：遍历金额从1到amount，对于每个金额，遍历硬币面额数组coins，计算最少需要的硬币数量。

a) 如果当前金额减去某个硬币面额大于等于0，并且dp[当前金额-硬币面额]+1的值小于dp[当前金额]，则更新dp[当前金额]为dp[当前金额-硬币面额]+1。

5. 返回结果：如果dp[amount]的值为无穷大，则表示无法凑出总金额，否则返回dp[amount]。

下面是一种实现该算法的C代码：

#include <stdio.h>
#include <limits.h>

int coinChange(int* coins, int coinsSize, int amount) {
    int dp[amount + 1];
    dp[0] = 0;
    
    for (int i = 1; i <= amount; i++) {
        dp[i] = INT_MAX;
        
        for (int j = 0; j < coinsSize; j++) {
            if (i - coins[j] >= 0 && dp[i - coins[j]] != INT_MAX) {
                dp[i] = (dp[i - coins[j]] + 1) < dp[i] ? (dp[i - coins[j]] + 1) : dp[i];
            }
        }
    }
    
    return dp[amount] == INT_MAX ? -1 : dp[amount];
}

int main() {
    int coins[] = {1, 2, 5};
    int coinsSize = sizeof(coins) / sizeof(coins[0]);
    int amount = 11;
    
    int result = coinChange(coins, coinsSize, amount);
    
    printf("Minimum number of coins required: %d\n", result);
    
    return 0;
}

这段代码中，我们使用了一个一维数组dp来保存状态，通过遍历硬币面额和金额，不断更新dp数组中的值，最终返回dp[amount]作为结果。注意在代码中INT_MAX表示无穷大，-1表示无法凑出总金额。

希望能帮到你！如果有任何问题，请随时提问。