算法系列--动态规划--背包问题(4)--完全背包拓展题目（上）
https://developer.aliyun.com/article/1480858?spm=a2c6h.13148508.setting.14.5f4e4f0ehYGFJx
💕"这种低水平质量的攻击根本就不值得我躲！"💕
作者：Lvzi
文章主要内容：算法系列–动态规划–背包问题(4)–完全背包拓展题目
大家好,今天为大家带来的是
算法系列--动态规划--背包问题(4)--完全背包拓展题目
2.零钱兑换II
链接:
https://leetcode.cn/problems/coin-change-ii/
分析:
本题就是统计情况数
这道题就是完全背包版本的
目标和
代码:
class Solution { public int change(int amount,int[] coins) { int n = coins.length; int[][] dp = new int[n + 1][amount + 1];// 创建dp表 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] >= 0) dp[i][j] += dp[i][j - coins[i - 1]]; } } return dp[n][amount]; } }
空间优化:
class Solution { public int change(int amount,int[] coins) { int n = coins.length; int[] dp = new int[amount + 1];// 创建dp表 dp[0] = 1;// 初始化 // 填表 for(int i = 1; i <= n; i++) for(int j = coins[i - 1]; j <= amount; j++) dp[j] += dp[j - coins[i - 1]]; return dp[amount]; } }
三.完全平方数
链接:
https://leetcode.cn/problems/perfect-squares/
分析:
本题分析下来,要完成的操作就是使用尽可能少的完全平方数表示n,每个完全平方数的数目是无限制的(挑选的物品无限制就很有可能是完全背包问题)
注意这里最重要返回的结果是组合数最少的,其余的思路和完全背包问题一致,不做过多的讲解
class Solution { public int numSquares(int n) { int m = (int)Math.sqrt(n);// 求出数组的长度 int[][] dp = new int[m + 1][n + 1];// 创建dp表 for(int j = 1; j <= n; j++) dp[0][j] = 0x3f3f3f3f;// 初始化 for(int i = 1; i <= m; i++) { for(int j = 1; j <= n; j++) { dp[i][j] = dp[i - 1][j]; if(j - i * i >= 0) dp[i][j] = Math.min(dp[i][j],dp[i][j - i * i] + 1); } } return dp[m][n]; } }
空间优化后的代码
class Solution { public int numSquares(int n) { int m = (int)Math.sqrt(n);// 求出数组的长度 int[] dp = new int[n + 1];// 创建dp表 for(int j = 1; j <= n; j++) dp[j] = 0x3f3f3f3f;// 初始化 for(int i = 1; i <= m; i++) for(int j = i * i; j <= n; j++) dp[j] = Math.min(dp[j],dp[j - i * i] + 1); return dp[n]; } }
