当前位置：首页 > article >正文

Leetcode 518 零钱兑换 II

article 2024/11/28 16:36:21

题意理解：

        给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。

        请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。

将coins看作不同重量的背包，然后把要凑成的组合数看作背包容量。

则该问题就是一个完全背包问题：

即使用重量为coins的物品，每个物品有无数个，装满大小为amount的背包有多少种装法。

解题思路：

首先理解题意，将题目转换为完全背包问题。

其中递归函数为：

dp[j]表示凑满target有n种方式

for(int i=0;i<coins.length;i++)

dp[j]+=dp[j-coins[i]]

关于遍历顺序：

1.遍历顺序问题

比如：amount=3 coins=[1,2]

先目硬币后目标值：

public int change22(int amount, int[] coins) {
        //dp[target]数组表示，凑出target,有dp[target]种方法
        int[] dp=new int[amount+1];
        Arrays.fill(dp,0);
        dp[0]=1;
        for(int i=0;i<coins.length;i++){
            for(int target=0;target<=amount;target++){
                System.out.println("target:"+target);
                if(target>=coins[i]){
                    System.out.print("硬币:"+coins[i]+"\t\t");
                    dp[target]+=dp[target-coins[i]];
                }
                print(dp);
            }

        }
        return dp[amount];
    }

target:0
1   0   0   0
target:1
硬币:1       1   1   0   0
target:2
硬币:1       1   1   1   0
target:3
硬币:1       1   1   1   1
target:0
1   1   1   1
target:1
1   1   1   1
target:2
硬币:2       1   1   2   1
target:3
硬币:2       1   1   2   2
2

其中，target=0时，有一种方式：没有一个硬币

target=1时，一种方式一个硬币 1

target=2时，两种方式： 1+1 2

target=3时，两种方式： 1+1+1 2+1|1+2

所以可以看出，这里先硬币后目标值，是组合数，所以1+2 和2+1 是同一个方式

先目标值后硬币：

public int change(int amount, int[] coins) {
        //dp[target]数组表示，凑出target,有dp[target]种方法
        int[] dp=new int[amount+1];
        Arrays.fill(dp,0);
        dp[0]=1;
        for(int target=0;target<=amount;target++){
            System.out.println("target:"+target);
            for(int i=0;i<coins.length;i++){

                if(target>=coins[i]){
                    System.out.print("硬币:"+coins[i]+"\t\t");
                    dp[target]+=dp[target-coins[i]];
                }
            }
            print(dp);
        }
        return dp[amount];
    }

target:0

1   0   0   0
target:1
硬币:1
1   1   0   0
target:2
硬币:1       硬币:2
1   1   2   0
target:3
硬币:1       硬币:2
1   1   2   3
3

其中，凑出target=0,有一种方式：一个硬币也没有

凑出target=1,有一种方式：有一个硬币

凑出target=2有两种方式： 1+1 2

凑出target=3有三种方式： 1+1+1 2+1 1+2

所以可以得出，先目标值后硬币，是排序数，2+1 和1+2是两种方式

总结：

先硬币后目标值：组合数

先目标值后硬币：排序数

先遍历硬币，后遍历目标值，对于3来说

dp[3]=dp[2]+dp[1]

使用硬币1： 1+1+1 一种方式 dp[2]=1,当且仅当仅有硬币1的时候，凑成3有一种方式

使用硬币2： 2+1 一种方式 dp[1]=1,当且仅当仅有硬币1和2的时候时，放入2，只有2+1一种方式凑成3

先遍历目标值，后遍历硬币时，对于3来说：

dp[3]=dp[2]+dp[1]

dp[2]=2 其中： 1+1 2——> 1+1+1 2+1

dp[1]=1 其中： 1 ——>1+2

2.求解

 public int change(int amount, int[] coins) {
        //dp[target]数组表示，凑出target,有dp[target]种方法
        int[] dp=new int[amount+1];
        Arrays.fill(dp,0);
        dp[0]=1;
        for(int i=0;i<coins.length;i++){
            for(int target=0;target<=amount;target++){
                if(target>=coins[i]){
                    dp[target]+=dp[target-coins[i]];
                }
            }
        }
        return dp[amount];
    }