leetcode第518零钱兑换

题目类型：完全背包求种类的个数

二维dp：

​ 分析：

• 完全背包dp数组的定义：0 - i个物品，放在容量为j的背包中，有多少种形式
• dp数组的初始化，物品数量为0的时候，不管容量为多大，均为0，背包容量为0的时候，我只有一种方式，就是不往背包里面放
• 状态转移方程的推导：如果当前背包的容量没有钱币的数值大，背包里面就放不进去，可是背包的容量没变啊，只能看这个物品的前面的物品放在当前背包的情况是怎么样的，如果当前背包的容量大于等于当前的货币，背包里面放的进去，现在背包的容量为i - 当前的货币值，这几种货币放在容量为j - count有几种情况，当前货币放的进去这是当前货币的的数量，还要加上我以前前i个物品能放在物品中的方法数。

class Solution
    public int change(int amount, int[] coins) {
        //这种题目感觉多少是有点不好理解，十分典型的完全背包问题
        int[][] dp = new int[coins.length + 1][amount + 1];
        //dp数组的定义：以0 - i个coins结尾的硬币，当背包容量为j时  有多少种排列的方式，
        //dp初始化  dp【i】【0】 = 1；当背包容量为0的时候，只有一种方式，那就是不放
        for(int i = 0;i < dp.length;i++){
            dp[i][0] = 1;
        }
        //动态规划代码
        for(int i = 1;i < dp.length;i++){
            for(int j =  1;j < dp[i].length;j++){
                if(j - coins[i - 1] >= 0){
                    dp[i][j] = dp[i - 1][j] + dp[i][j - coins[i - 1]] ;
                }else{
                    dp[i][j] = dp[i - 1][j];
                }
            }
            for(int k = 0;k < dp.length;k++){
                for(int z = 0;z < dp[k].length;z++){
                    System.out.print(dp[k][z] + " ");
                }
                System.out.println();
            }
             System.out.println("=========");

        }

        return dp[coins.length][amount];

    }
}

一维dp：

**一维dp数组的定义：**容量为j的背包有有多少中装进背包方法

**dp数组的初始化：**dp【0】 = 1 容量为0的背包有1种装钱币的方法，就是1

**状态转移方程的推导：**容量为j的背包 在当前货币下 能够有多少种装进背包的方法 = 容量为j的背包在前一个货币上有多少种方法 + 容量为j - coins【i】的背包下，有多少中装货币的方法。

注意：

1. 在求装满背包有几种方案时，先遍历物品，在遍历背包，求的是组合
2. 先遍历背包，在遍历物品属于排列。

class Solution {
    public int change(int amount, int[] coins) {
        int[] dp = new int[amount + 1];
        dp[0] = 1;
        for(int i = 0;i < coins.length;i++){
            for(int j = coins[i];j <= amount;j++){
                dp[j] += dp[j - coins[i]];
            }
        }

        return dp[amount];
    }
}