leetcode322：零钱兑换

题目链接

leetcode

题目描述

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。
你可以认为每种硬币的数量是无限的。

C++ 代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

/*
    完全背包问题

    状态定义：
        f[i][j] 表示使用前 i 个硬币面额组成金额 j，最少的硬币个数。
    状态转移方程：
        对于每个硬币面额 coins[i]，遍历所有可能的金额 j
        j 小于当前硬币面额
            f[i+1][j] = f[i][j]
        j 大于等于当前硬币面额
            f[i+1][j] = min(f[i][j], f[i+1][j-coins[i]] + 1)
    初始状态：
        f[0][0] = 0
    答案：
        f[n][amount]
        表示使用前 n 个硬币组成金额 amount，最少的硬币个数。

    时间复杂度：O(nm)
        其中 n 表示硬币种数，m 表示总金额，两层循环。
        状态数为 O(m)，转移总数为 O(n)，每次转移的时间复杂度为 O(1)，
        时间复杂度为 O(nm)。
    空间复杂度：O(nm)
*/
class Solution_1 {
public:
    int coinChange(vector<int>& coins, int amount) {
        int n = coins.size();
        vector<vector<int>> f(n+1, vector<int>(amount+1, amount+1));
        // 状态初始化
        f[0][0] = 0;

        // 状态计算
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= amount; j++) {
                if (j < coins[i]) {
                    f[i+1][j] = f[i][j];
                } else {
                    f[i+1][j] = min(f[i][j], f[i+1][j-coins[i]] + 1);
                }
            }
        }
        
        return f[n][amount] != amount+1 ? f[n][amount] : -1;
    }
};

/*
    优化空间

    时间复杂度：O(nm)
    空间复杂度：O(m)
*/
class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> f(amount+1, amount+1);
        // 状态初始化
        f[0] = 0;

        // 状态计算
        for (int i = 0; i < coins.size(); i++) {
            for (int j = coins[i]; j <= amount; j++) {
                f[j] = min(f[j], f[j-coins[i]] + 1);
            }
        }

        return f[amount] != amount+1 ? f[amount] : -1;
    }
};

// 辅助函数：打印数组
void printArray(const vector<int>& nums) {
    cout << "[";
    for (size_t i = 0; i < nums.size(); i++) {
        cout << nums[i];
        if (i != nums.size() - 1) cout << ",";
    }
    cout << "]";
}

int main() {
    Solution solution;
    vector<vector<int>> coins_cases = {
        {1,2,5},
        {2},
        {1}
    };
    vector<int> amount_cases = { 
        11, 3, 0 
    };

    for (int i = 0; i < coins_cases.size(); i++) {
        vector<int> coins = coins_cases[i];
        int amount = amount_cases[i];

        cout << "Input: coins = ";
        printArray(coins);
        cout << ", amount: " << amount << endl;   
        int result = solution.coinChange(coins, amount);
        cout << "Output: " << result << endl;
    }

    return 0;
}