leetcode322：零钱兑换

题目链接

leetcode

题目描述

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

C++ 代码

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

void printArray(vector<int>& arr) {
    for (int i = 0; i < arr.size(); i ++) {
        if (i != arr.size() - 1) cout << arr[i] << " ";
        else cout << arr[i];
    }
}

/*
    记忆化搜索 = 递归搜索 + 保存计算结果（备忘录）

    时间复杂度：O(nm)
        其中 n 表示硬币种数，m 表示总金额，总共两层循环。
    空间复杂度：O(m)
*/
class Solution_0 {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> memo(amount + 1, INT_MAX); // 初始化备忘录数组，INT_MAX表示无法兑换
        memo[0] = 0;
        return dfs(coins, amount, memo);
    }

    int dfs(const vector<int>& coins, int amount, vector<int>& memo) {
        if (amount < 0) return -1;
        if (amount == 0) return 0;
        // 查备忘录，防止重复计算
        if (memo[amount] != INT_MAX) return memo[amount];

        int res = INT_MAX;
        for (const int& coin : coins) {
            int subProblem = dfs(coins, amount - coin, memo);
            if (subProblem == -1) continue;
            res = min(res, subProblem + 1);
        }
        // 把计算结果存入备忘录
        memo[amount] = (res == INT_MAX) ? -1 : res;
        return memo[amount];
    }
};

/*
    等价于完全背包问题

    状态定义：
        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));
        
        // base case
        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);
                }
            }
        }
        int res = f[n][amount];
        return res != amount + 1 ? res : -1;
    }
};

/*
    优化空间

    状态表示：
        f[j] 表示凑出 j 的金额，最少需要多少个硬币。
    状态计算：
        第 i 种硬币更新 f[j]：
            f[j] = min(f[j], f[j - coins[i]] + 1)
    遍历顺序：
        第一层循环枚举不同硬币，
        第二层循环从小到大枚举所有面额（由于每种硬币有无限多个，所以从小到大枚举）。

    时间复杂度：O(nm)
        其中 n 表示硬币种数，m 表示总金额，总共两层循环。
    空间复杂度：O(m)
*/
class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> f(amount + 1, amount + 1);
        // base case
        f[0] = 0;
        // for (int i = 0; i <= amount; i ++) {
        //     for (int coin : coins) {
        //         if (i >= coin) {
        //             f[i] = min(f[i], f[i - coin] + 1);
        //         }
        //     }
        // }
        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 ? -1 : f[amount];
    }
};

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

    for (int i = 0; i < test_case.size(); i ++) {
        vector<int> coins = test_case[i];
        int amount = amounts[i];
        cout << "coins: ";
        printArray(coins);
        cout << ", amount: " << amount << endl;   
        int result = solution.coinChange(coins, amount);
        cout << "result: " << result << endl;
    }

    return 0;
}

Golang 代码

package main

import (
	"fmt"
	"math"
)

/*
   动态规划：
       使用一个数组 dp，其中 dp[i] 表示凑成金额 i 所需的最少硬币数量。
       初始化 dp[0] = 0，因为金额为 0 时，需要 0 个硬币。
       对于每个金额 i，遍历所有硬币，如果 i-coin >= 0，则更新 dp[i] 为 dp[i-coin] + 1 的最小值。
   边界条件：
       如果 dp[amount] 仍然是 math.MaxInt32，说明无法凑成 amount，返回 -1。

    时间复杂度：O(mn)
        其中 n 表示硬币种数，m 表示总金额，总共两层循环。
        遍历每个金额和每个硬币，时间复杂度为 O(mn)。
    空间复杂度：O(m)
        使用了一个大小为 m+1 的数组 dp，空间复杂度为 O(m)。
*/
// coinChange 返回凑成金额 amount 所需的最少硬币数量
func coinChange(coins []int, amount int) int {
    dp := make([]int, amount+1)
	for i := range dp {
		dp[i] = math.MaxInt32
	}
	dp[0] = 0 // 金额为 0 时，需要 0 个硬币

	for i := 1; i <= amount; i ++ {
		for _, coin := range coins {
			if i - coin >= 0 && dp[i - coin] != math.MaxInt32 {
				dp[i] = min(dp[i], dp[i-coin]+1)
			}
		}
	}

	if dp[amount] == math.MaxInt32 {
		return -1 // 如果 dp[amount] 仍然是 MaxInt32，说明无法凑成 amount
	}
	return dp[amount]
}

func main() {
	// 测试用例
	testCases := []struct {
		coins   []int
		amount  int
		expected int
	}{
		{
			coins:   []int{1, 2, 5},
			amount:  11,
			expected: 3,
		},
		{
			coins:   []int{2},
			amount:  3,
			expected: -1,
		},
		{
			coins:   []int{1},
			amount:  0,
			expected: 0,
		},
	}

	for i, tc := range testCases {
		result := coinChange(tc.coins, tc.amount)
		fmt.Printf("Test Case %d, Input: coins = %v, amount = %d\n", i+1, tc.coins, tc.amount)
		if result == tc.expected {
			fmt.Printf("Test Case %d, Output: %d, PASS\n", i+1, result)
		} else {
			fmt.Printf("Test Case %d, Output: %d, FAIL (Expected: %d)\n", i+1, result, tc.expected)
		}
	}
}