首页 > 试题广场 >

兑换零钱(二)

[编程题]兑换零钱(二)
  • 热度指数:2617 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
给定一个整数数组 nums 表示不同数额的硬币和一个正整数 target 表示总金额,请你计算并返回可以凑出总金额的的组合数。如果凑不出 target 则返回 0。

数据范围:数组长度满足 ,数组中的数和 target 大小满足
示例1

输入

5,[1,2,4,5]

输出

5
示例2

输入

5,[4]

输出

0
示例3

输入

5,[5]

输出

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

暴力递归->记忆化搜索

从左往右尝试,depth表示当前第depth个面额及其之后的面额可以随意使用,rest为还剩下多少钱要凑。在递归的过程中有如下三种情况:
  1. rest=0,就表示形成了一种有效的方案;
  2. rest<0,当前的凑钱方案不合法,直接返回0;
  3. 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。根据递归中depthrest的取值可以发现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)
这道题,多少人知其然,却不知其所以然,我来解释一下,不废话直接上菜:

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)
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)
#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)
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)