LeetCode 面试题 08.11. 硬币

Categories:

题目描述
思路分析
1. 解法一：完全背包（推荐）
相似题目

题目描述

✅ 面试题 08.11. 硬币

思路分析

解法一：完全背包（推荐）

核心思路：

硬币面额固定为 1、5、10、25，要求组合数而非排列数。

采用一维 DP，dp[i] 表示凑成金额 i 的方案数。

按面额从小到大遍历，确保每种组合只计一次。

复杂度分析：

时间复杂度：O(n)，其中 n 表示金额大小。

空间复杂度：O(n)，用于一维 DP 数组。

class Solution {
    public int waysToChange(int n) {
        int[] coins = {1, 5, 10, 25};
        int mod = 1_000_000_007;

        int[] dp = new int[n + 1];
        dp[0] = 1;

        for (int coin : coins) {
            for (int i = coin; i <= n; i++) {
                dp[i] = (dp[i] + dp[i - coin]) % mod;
            }
        }

        return dp[n];
    }
}

func waysToChange(n int) int {
	coins := []int{1, 5, 10, 25}
	mod := 1000000007

	dp := make([]int, n+1)
	dp[0] = 1

	for _, coin := range coins {
		for i := coin; i <= n; i++ {
			dp[i] = (dp[i] + dp[i-coin]) % mod
		}
	}

	return dp[n]
}

相似题目

题目	难度	考察点
518. 零钱兑换 II	中等	完全背包
322. 零钱兑换	中等	动态规划
377. 组合总和 Ⅳ	中等	动态规划
279. 完全平方数	中等	完全背包
494. 目标和	中等	01 背包

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2024/57613487