我要招人

去企业版

首页 > 试题广场 >

兑换零钱(二)

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

热度指数：2333 时间限制：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)

牛客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)

提交观点

问题信息

动态规划数组

难度：

4条回答 76收藏 1577浏览

通过挑战的用户

查看代码

已注销

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

兑换零钱(二)

输入

输出

输入

输出

输入

输出

暴力递归->记忆化搜索

动态规划

问题信息

热门推荐

通过挑战的用户

相关试题