Leetcode 518 零钱兑换 II

题意理解：

        给你一个整数数组 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];
    }

3.分析

时间复杂度：

        O(n^2)

空间复杂度：

        O(n)