首页 > 试题广场 >

兑换零钱(二)

[编程题]兑换零钱(二)

热度指数：2809 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个整数数组 nums 表示不同数额的硬币和一个正整数 target 表示总金额，请你计算并返回可以凑出总金额的的组合数。如果凑不出 target 则返回 0。

数据范围：数组长度满足 $1 \le n \le 300 \$ ，数组中的数和 target 大小满足 $1 \le val \le 5000 \$

示例1

输入

5,[1,2,4,5]

输出

示例2

输入

5,[4]

输出

示例3

输入

5,[5]

输出

算法知识视频讲解

Java

pein531

老套路，暴力递归->记忆化搜索->动态规划

暴力递归->记忆化搜索

从左往右尝试，depth表示当前第depth个面额及其之后的面额可以随意使用，rest为还剩下多少钱要凑。在递归的过程中有如下三种情况：

rest=0，就表示形成了一种有效的方案；
rest<0，当前的凑钱方案不合法，直接返回0；
rest>0，使用递归从当前depth开始的面额继续凑目标值。

代码就不详细写了，直接用缓存法改一版记忆化搜索，防止递归展开的过程中重复计算。

private int recurrent(int[] nums, int depth, int rest, int[][] mem) {
    if(rest < 0){
        return 0;
    }
    if(rest == 0){
        return 1;
    }
    if(mem[depth][rest] > 0) return mem[depth][rest];
    for(int i = depth; i < nums.length; i++){
        mem[depth][rest] += recurrent(nums, i, rest - nums[i], mem);
    }
    return mem[depth][rest];
}

动态规划

然后根据递归的逻辑可以修改出动态规划的过程，dp[i][j]表示利用从i到最后一种面额凑j能有多少种方案。根据递归函数中的递归头确定base case，dp数组的第一列为1。根据递归中depth和rest的取值可以发现dp[i][j]依赖左边和下面的值，因此从下往上，从左往右填表。

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param target int整型 
     * @param nums int整型一维数组 
     * @return int整型
     */
    public int change (int target, int[] nums) {
        // write code here
        int n = nums.length;
        int[][] dp = new int[n][target + 1];
        for(int i = 0; i < n; i++){
            dp[i][0] = 1;
        }
        for(int i = n - 1; i >= 0; i--){
            for(int j = nums[i]; j <= target; j++){
                dp[i][j] = (i < n - 1? dp[i + 1][j]: 0) + dp[i][j - nums[i]];
            }
        }
        return dp[0][target];
    }
}

最后我们注意到，dp[i][j]只依赖其下一行及左边的值，因此还可以进行空间压缩，dp用一维数组就可以，这也就是我们经常看到的背包问题解法。

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param target int整型 
     * @param nums int整型一维数组 
     * @return int整型
     */
    public int change (int target, int[] nums) {
        // write code here
        int n = nums.length;
        int[] dp = new int[target + 1];
        dp[0] = 1;
        for(int i = n - 1; i >= 0; i--){
            for(int j = nums[i]; j <= target; j++){
                dp[j] += dp[j - nums[i]];
            }
        }
        return dp[target];
    }
}

编辑于 2021-12-15 16:07:43 回复(0)

Java

唐氏综合征

这道题，多少人知其然，却不知其所以然，我来解释一下，不废话直接上菜：

1. 第一种解法（错误解法，把顺序算进去了）

 public static int change(int target, int[] nums) {
        // write code here
        // dp[i] 表示凑出金额 i 的组合数
        int[] dp = new int[target + 1];
        dp[0] = 1;// 什么都不取，直接凑成0，因此为1，这是后续的启动
        for (int i = 1; i <= target; i++) {
            // 选择每种金额的前提下，找到凑出 i 的可能数，并相加
            for (int money : nums) {
                // 只有金额比当前i小，才可能凑出来
                if (money <= i) {
                    dp[i] += dp[i - money];
                }
            }
        }
        return dp[target];
    }

解释：对于外层遍历 target，内层遍历 nums 的解法，咋一看是没问题，但仔细想想会发现这种解法考虑所有的排列组合形式，当我们求解 dp[i] 的时候，在当前元素为 money 的情况下，i （i >= money, 否则无法凑成i），我们知道 money 可以与 dp[i - money] 的所有组合构成 dp[i]，但我们是首先择了 money 作为前提，如果后续遍历到 second, second 与 money 组合也能凑成 i ，则组成i 的方式有了 [money, second] 和 [second, money]，很明显这是重复了，因此结果会偏大，只是举了最简单的例子说明了一下问题

二：正确的解法如下

  public static int change(int target, int[] nums) {
        int[] dp = new int[target + 1];
        dp[0] = 1;// 什么都不取，直接凑成0，因此为1，这是后续的启动
        for (int money : nums) {
            for (int i = 1; i <= target; i++) {
                // 对于每个money 更新每个 target
                // 如果 i 比 money还小，选择 money 的前提下，无法凑成 目标值
                if (i - money >= 0)
                    dp[i] += dp[i - money];
            }
        }
        return dp[target];
    }

解释：我们可以先遍历 nums ，再考虑遍历 target, 这就类似于背包问题了，这种方式最直接的好处就是可以有效避免组合重复问题，因为我遍历到 nums 的元素 first 时，如果 i - first > 0 , 则只有当 dp[i- first] 已经计算出来了，才会正确的更新 dp[i] 的值, 因此两两元素前后位置不同时仅计算一次，如果是多个元素构成目标值时亦是如此，比如目标值9，元素有 1,3,5，当前元素1时, dp[9] += dp[8]， dp[8] 又可以细分为当前元素3时 dp[5], 当前元素5 时 dp[3]，计算dp[8] 时，只有当 dp[3] 更新后，到达了 dp[5] 才能计算出来，因此忽略了顺序（全是1的组合暂时忽略下）

发表于 2024-07-23 15:17:50 回复(1)

牛客512061010号

PYthon：

class Solution:
    def change(self, target: int, nums: List[int]) -> int:
        dp = [0] * (target + 1)
        dp[0] = 1
        for num in nums:
            for i in range(num, target + 1):
                dp[i] += dp[i - num]
        return dp[target]

JS：

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * @param target int整型
 * @param nums int整型一维数组
 * @return int整型
 */
function change(target, nums) {
    const dp = new Array(target + 1).fill(0);
    dp[0] = 1;
    for (const num of nums) {
        for (let i = num; i <= target; i++) {
            dp[i] += dp[i - num];
        }
    }
    return dp[target];
}

module.exports = {
    change: change
};

发表于 2023-12-07 10:12:49 回复(0)

C++

阿金要努力

#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param target int整型 
     * @param nums int整型vector 
     * @return int整型
     */
    int change(int target, vector<int>& nums) 
    {
        // write code here
        vector<int> dp(target+1, 0);
        dp[0]=1;
        for(int i=0;i<nums.size();i++)
        {
            for(int j=nums[i];j<=target;j++)
            {
                dp[j]+=dp[j-nums[i]];
            }
        }
        return dp[target];
    }
};

发表于 2023-03-15 11:50:49 回复(0)

lizi-hust

import java.util.*;
public class Solution {
    public int change (int target, int[] nums) {
        int n = nums.length;
        int[][] dp = new int[n+1][target+1];
        for(int i=0; i<=n; i++) dp[i][0] = 1;
        
        for(int i=1; i<=n; i++){
            for(int j=1; j<=target; j++){
                if(j - nums[i-1] >= 0)
                    dp[i][j] = dp[i-1][j] + dp[i][j-nums[i-1]];
                else 
                    dp[i][j] = dp[i-1][j];
            }
        }
        return dp[n][target];
    }
}

发表于 2022-07-22 21:40:47 回复(0)

提交观点

问题信息

动态规划数组

难度：

5条回答 95收藏 2946浏览

通过挑战的用户

查看代码

已注销

2023-03-05 10:55:00
牛客59979...

2022-11-04 14:00:14
JhaStinger

2022-09-25 23:09:02
盛夏的泡沫

2022-09-16 12:57:20
ekile

2022-09-14 13:08:39

兑换零钱(二)

输入

输出

输入

输出

输入

输出

暴力递归->记忆化搜索

动态规划

问题信息

热门推荐

通过挑战的用户

相关试题