【动态规划】心有惊雷，生似静湖 - 10. 完全背包问题

1. 零钱兑换

题目链接: 518. 零钱兑换 II

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

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

假设每一种面额的硬币有无限个。

题目数据保证结果符合 32 位带符号整数。

示例 1：

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

输入：amount = 3, coins = [2] 输出：0 解释：只用面额 2 的硬币不能凑成总金额 3 。 示例 3：

输入：amount = 10, coins = [10] 输出：1

第一 动态规划

1. 状态表示 dp[i][j] 表示在前 i 个硬币中选,总金额等于 j 的不同选法的数目.

2. 状态转移方程 以最后一个位置选择的个数来划分情况: coins[i] 不选, dp[i][j] = dp[i-1][j]; coins[i] 选一个, dp[i][j] = dp[i-1][j-coins[i]]; coins[i] 选两个, dp[i][j] = dp[i-1][j-2coins[i]]; coins[i] 选k个, dp[i][j] = dp[i-1][j-kcoins[i]]; 综合题意可知: dp[i][j] = dp[i-1][j] + dp[i-1][j-coins[i]] + dp[i-1][j-2coins[i]] +…+ dp[i-1][j-kcoins[i]]; ① 又当①中 j = j-coins[i] 时有: dp[i][j-coins[i]] = dp[i-1][j-coins[i]] + … + dp[i-1][j-xcoins[i]];② 而dp[i][j] 的定义决定了 j-kcoins[i] 和 j-x*coins[i]无限接近于0,故 k = x; 由①②两式可得: dp[i][j] = dp[i-1][j] + dp[i][j-coins[i]]; dp[i][j-coins[i]]使用时需要满足 j >= coins[i]. 同时选择的硬币不一定能够刚好等于 j . 将不等于 j 的情况 初始化为0(不能初始化为-1,否则在+=的时候会影响结果). 不知道此处为什么这样处理的可以去看我上篇文章的第一道题链接: 动态规划-9.

3. 初始化 多创建了一行一列,需要处理两个细节问题: 1. dp表与coins数组下标之间的对应关系: i – i-1, j – j-1; 2.初始化虚拟节点: 第一列中满足 j >= coins[i]的只有第一个位置,其他的不做初始化,dp[0][0] 表示的是在没有硬币的时候,满足总金额 j = 0的选法有几种,很显然就是一种:不选. 所以dp[0][0] = 1; 第一行中dp[0][0] = 1, 其余位置均达不到 j ,所以全部初始化为0;

4. 填表顺序 根据dp[i][j] = dp[i-1][j] + dp[i][j-coins[i]]; 可知若是想知道dp[i][j]就得先求等式后面两个. 所以从上往下填写每一行.

5. 返回值 根据题意返回 dp[coins.length][amount];

第二 代码实现

class Solution {
    //优化前:
    // public int change(int amount, int[] coins) {
    //     int n = coins.length;
    //     int[][] dp = new int[n+1][amount+1];
    //     dp[0][0] = 1;
    //     for(int i = 1;i <= n;i++) {
    //         for(int j = 0;j <= amount;j++) {
    //             dp[i][j] += dp[i-1][j];
    //             if(j >= coins[i-1] && dp[i][j-coins[i-1]] != 0) {
    //                 dp[i][j] += dp[i][j-coins[i-1]];
    //             }
    //         }
    //     }
    //     return dp[n][amount];
    // }

    //优化后:
    public int change(int amount, int[] coins) {
        int n = coins.length;
        int[] dp = new int[amount+1];
        dp[0] = 1;
        for(int i = 1;i <= n;i++) {
            for(int j = 0;j <= amount;j++) {
                if(j >= coins[i-1] && dp[j-coins[i-1]] != 0) {
                    dp[j] += dp[j-coins[i-1]];
                }
            }
        }
        return dp[amount];
    }
}

以上代码若是不知道为何要这么优化的可以看我上篇文章的第一道题链接: 动态规划-9.

2. 完全平方数

题目链接: 279. 完全平方数

题目内容:

给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。

完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

示例 1：

输入：n = 12 输出：3 解释：12 = 4 + 4 + 4 示例 2：

输入：n = 13 输出：2 解释：13 = 4 + 9

第一 动态规划

1. 状态表示 dp[i][j] 表示在前 i 个位置选, 总和等于 j 的不同的选法中,所用完全平方数的最少数量.

2. 状态转移方程 根据最后一个位置的选择情况来划分问题: ii 不选, dp[i][j] = dp[i-1][j]; ii 选一次, dp[i][j] = dp[i-1][j-ii] + 1; ii 选两次, dp[i][j] = dp[i-1][j-2ii] + 2; ii 选k次, dp[i][j] = dp[i-1][j-kii] + k; 根据题意,dp[i][j] = min(dp[i-1][j],dp[i-1][j-ii]+1,…,dp[i-1][j-kii]+k);① dp[i][j-ii] +1 = min(dp[i-1][j-ii]+1,dp[i-1][j-2ii]+2,…,dp[i-1][j-kii]+k);② 由①②可得: dp[i][j] = Math.min(dp[i-1][j],dp[i][j-ii]+2); ③ ③式需要满足 j >= ii; dp[i][j]中定义的是恰好等于 j 的情况,但会出现不等于 j 的情况, 根据题意要求min,所以将这种情况初始化为0x3f3f3f3f(最大值的一半). 所以③式还需要满足 dp[i][j-i*i] != 0x3f3f3f3f;

3. 初始化 多创建一行一列,需要处理两个细节问题: 1. dp表与 完全平方数组之间的对应关系: i – i-1 , j – j-1 2. 初始化虚拟节点: 第一列只有dp[0][0]满足 j > i*i, 此处需要默认0是完全平方数, 即使题目的例子是从1开始的. 因此dp[0][0] = 1; 第一行的初始化与上题一致.

4. 填表顺序 由状态转移方程可知:从左往右开始填写每一行.

5. 返回值 返回dp[n][n]

第二 代码实现

class Solution {
    public int numSquares(int n) {
        //优化前:
        int m = (int)Math.sqrt(n);
        int[][] dp = new int[m+1][n+1];
        //2.初始化
        // dp[0][0] = 1;
        for(int i = 1;i <= n;++i) {
            dp[0][i] = 0x3f3f3f3f;
        }
        //3. 填表
        for(int i = 1;i <= m;++i) {
            for(int j = 0;j <= n;++j) {//j需要从0开始,因为初始化的时候并没有考虑第一列的全部位置,只考虑了第一列的第一个位置.
                dp[i][j] = dp[i-1][j];
                if(j >= i*i && dp[i][j-i*i] != 0x3f3f3f3f) {
                    dp[i][j] = Math.min(dp[i-1][j],dp[i][j-i*i]+1);
                }
            }
        }
        return dp[m][n];
        
        //优化后:
        // int[] dp = new int[n+1];
        // //2.初始化
        // // dp[0][0] = 1;
        // for(int i = 1;i <= n;++i) {
        //     dp[i] = 0x3f3f3f3f;
        // }
        // //3. 填表
        // for(int i = 1;i <= n;++i) {
        //     for(int j = i*i;j <= n;++j) {
        //         if(dp[j-i*i] != 0x3f3f3f3f) {
        //             dp[j] = Math.min(dp[j],dp[j-i*i]+1);
        //         }
        //     }
        // }
        // return dp[n];
    }
}

本篇博客到这里就结束啦, 感谢观看 ❤❤❤

🐎期待与你的下一次相遇😊😊😊