2. 完全背包

零钱兑换(完全背包-求极值)

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。

示例
输入: coins = [1, 2, 5], amount = 11
输出: 3
解释: 11 = 5 + 5 + 1

回到凑零钱问题，为什么说它符合最优子结构呢？比如你想求 amount = 11 时的最少数（原问题），如果你知道凑出 amount = 10 的最少数（子问题），你只需要把子问题的答案加一（再选一枚面值为 1 的XXX）就是原问题的答案。因为XXX的数量是没有限制的，所以子问题之间没有相互制，是互相独立的。

1.暴力尝试
写出当面额是amount时，最少兑换数目

// 返回当面额是amount时，最少的兑换零钱数目
public static int way1(int[] coins, int amount){
    // base case: 当面额为0时，不需要兑换
    if (amount == 0){
        return 0;
    }
    if (amount < 0){
        // 无法兑换
        return -1;
    }
    // 第一轮的时候，挨个尝试，找到最小的
    int res = Integer.MAX_VALUE;
    for(int coin : coins){
        int subProblem = way1(coins, amount-coin);
        if(subProblem != -1) {
            res = Math.min(res, subProblem + 1);
        }
        // 子问题等于-1，是无效的
    }
    // 可能所有的子问题都是无效的，res还是没有改变过,就返回-1，表示无效解法
    return res == Integer.MAX_VALUE ? -1 : res;
}

2.记忆化搜索-备忘录
把已经得到的递归子树中的答案提前返回，避免不必要的计算, 其中数组初始化为-10，就是一种没有处理过的标志位，可以自行修改设计

// 记忆化搜索，优化上述的方法
public static int way2(int[] coins, int amount){
    int[] map = new int[amount+1];
    Arrays.fill(map, -10);
    return dp_2(coins, amount, map);
}

public static int dp_2(int[] coins, int amount, int[] map){
    if (amount == 0){
        map[amount] = 0;
        return 0;
    }
    if (amount < 0){
        return -1;
    }
    // 可能会返回amount 为负数的情况，所以要把base case放在前面，用HashMap就不用担心数组越界
    if (map[amount] != -10){
        return map[amount];
    }
    // 第一轮尝试
    int res = Integer.MAX_VALUE;
    for (int coin : coins){
        int subProblem = dp_2(coins, amount-coin, map);
        if (subProblem == -1){
            continue;
        }
        // 也可以在这里记录
        map[amount-coin] = subProblem;
        res = Math.min(res, subProblem + 1);
    }
    map[amount] = (res == Integer.MAX_VALUE ? -1 : res);
    return map[amount];
}

3.动态规划-从底向上

// 动态规划，用DP数据代替记忆化搜索
public static int way3(int[] coins, int amount){
    // 可变参数amount 0~amount
    int[] dp = new int[amount+1];
    // 设置数组的数, 都是正整数，最多用amount张
    Arrays.fill(dp, amount+1);
    // base case:
    dp[0] = 0;
    for(int i=1; i<=amount; i++){
        for(int coin : coins){
            // 无效尝试，直接下一个
            if(i-coin < 0){
                continue;
            }
            // dp[i]的答案由，dp[i-coin]方案中最少的+1得到
            dp[i] = Math.min(dp[i], 1+dp[i-coin]);
        }
    }
    return dp[amount] == amount+1 ? -1: dp[amount];
}

零钱兑换(完全背包-求方案数)

给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。

输入: amount = 5, coins = [1, 2, 5]
输出: 4
解释: 有四种方式可以凑成总金额:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

1.暴力尝试

每个面值都要挨个尝试，因为不是0-1问题，所以会出现计数选择

// 暴力递归方法: 时间复杂度->O(aimˆN), 非常高
// @ arr: 面值数组; @ index: 对第index的面试的决策; @ res: 还有多少钱凑够面值
public static int way1_process(int[] arr, int index, int res){
    // base case: arr数组都选择完毕，res如果能成功为0，成功方法数返回1，如果不为0，不返回
    if (index == arr.length) {
        return res==0 ? 1: 0;
    }
    // 每次对index的决策，都包括从0张到最接近res的张数
    int ways = 0;
    for(int zhang = 0; res - arr[index]*zhang>=0; zhang++){
        ways += way1_process(arr, index+1, res-zhang*arr[index]);
    }
    return ways;
}
public static int way1(int[]arr, int aim){
    if(arr==null || aim<0 || arr.length==0){
        return 0;
    }
    return way1_process(arr, 0, aim);
}

2.动态规划

// 动态规划
// 时间复杂度: O(N*aimˆ2)
// 牛客记录: 124ms, 26000K
public static int way2(int[] arr, int aim){
    // 可变参数: index 和 res
    // index:[0~arr.length] res:[0~aim], 设置数组dp[arr.length+1][aim+1]
    int N = arr.length;
    int[][] dp = new int[N+1][aim+1];
    // 初始位置
    dp[N][0] = 1;
    // 普通位置计算
    for (int index = N-1; index>=0; index--){
        for (int res = 0; res<=aim; res++){
            int ways = 0;
            for(int zhang = 0; res - arr[index]*zhang>=0; zhang++){
                ways += dp[index+1][res-arr[index]*zhang];
            }
            dp[index][res] = ways;
        }
    }
    return dp[0][aim];
}

3.斜率优化后的DP

通过观察可以得到，dp[index][res]是由下面的点dp[index+1][res] 和 左面的点dp[index][res-arr[index]]组成, 如果左面的点存在

// 直接改进成，空间优化的动态规划
// 牛客记录: 52ms, 26000K
public static int way3(int[] arr, int aim){
    // 可变参数: index 和 res
    // index:[0~arr.length] res:[0~aim], 设置数组dp[arr.length+1][aim+1]
    int N = arr.length;
    int[][] dp = new int[N+1][aim+1];
    // 初始条件
    dp[N][0] = 1;
    // 一般位置
    for (int index = N-1; index>=0; index--){
        for (int res = 0; res <= aim; res++){
            // 时间优化之 斜率优化，观察之前循环累加，优化得到
            dp[index][res] = dp[index+1][res];
            if(res - arr[index] >= 0){
                dp[index][res] += dp[index][res-arr[index]];
            }
        }
    }
    return dp[0][aim];
}

4.空间压缩TODO
j