目录
322. 零钱兑换
279. 完全平方数
139.单词拆分
多重背包理论基础
322. 零钱兑换
题解
322. 零钱兑换 - 力扣(LeetCode)
给你一个整数数组 coins
,表示不同面额的硬币;以及一个整数 amount
,表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额,返回 -1
。
你可以认为每种硬币的数量是无限的。
示例 1:
输入:coins = [1, 2, 5], amount = 11
输出:3
解释:11 = 5 + 5 + 1
示例 2:
输入:coins = [2], amount = 3
输出:-1
示例 3:
输入:coins = [1], amount = 0
输出:0
提示:
1 <= coins.length <= 12
- 1 <= coins[i] <= 231 - 1
- 0 <= amount <= 104
思路
代码随想录:322.零钱兑换
视频讲解:LeetCode:322.零钱兑换
转换为完全背包理论:
动态规划五部曲:
- 确定dp数组以及下标的含义:
dp[j]
为凑足总金额 j 所需的最少硬币个数。 - 确定递推公式:
dp[j] = min(dp[j - coins[i]] + 1, dp[j])
。 - 数组初始化:凑够金额 0 的硬币个数为 0,所以
dp[0] = 0
,由于递推公式中获取的是 min,所以非 0 下标应该初始化为一个比较大的数,如Integer.MAX_VALUE
或amount + 1
,由于题目提示中告知amount <= 10000
,所以也可以初始化为10001。 - 确定遍历顺序:本题求的是硬币最小个数,可以选择外层遍历物品内层遍历背包(反过来也可以),由于是完全背包类型,所以选择顺序遍历。
- 举例推导:
题解
java"> class Solution {public int coinChange(int[] coins, int amount) {int[] dp = new int[amount + 1];for (int i = 0; i < dp.length; i++) {dp[i] = 10001;}dp[0] = 0;for (int i = 0; i < coins.length; i++) {for (int j = coins[i]; j <= amount; j++) {dp[j] = Math.min(dp[j - coins[i]] + 1, dp[j]);}}if (dp[amount] == 10001)return -1;return dp[amount];}
}
279. 完全平方数
题目
279. 完全平方数 - 力扣(LeetCode)
给你一个整数 n
,返回 和为 n
的完全平方数的最少数量 。
完全平方数 是一个整数,其值等于另一个整数的平方;换句话说,其值等于一个整数自乘的积。例如,1
、4
、9
和 16
都是完全平方数,而 3
和 11
不是。
示例 1:
输入:n = 12
输出:3
解释:12 = 4 + 4 + 4
示例 2:
输入:n = 13
输出:2
解释:13 = 4 + 9
提示:
- 1 <= n <= 104
思路
代码随想录:279.完全平方数
视频讲解:LeetCode:279.完全平方数
同上一题322. 零钱兑换
题解
java">class Solution {public int numSquares(int n) {int[] dp = new int[n + 1];for (int i = 0; i < dp.length; i++) {dp[i] = 10001;}dp[0] = 0;for (int i = 1; i * i <= n; i++) {for (int j = i * i; j <= n; j++) {dp[j] = Math.min(dp[j - i * i] + 1, dp[j]);}}return dp[n];}
}
139.单词拆分
题目
139. 单词拆分 - 力扣(LeetCode)
给你一个字符串 s
和一个字符串列表 wordDict
作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s
则返回 true
。
**注意:**不要求字典中出现的单词全部都使用,并且字典中的单词可以重复使用。
示例 1:
输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。
示例 2:
输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapple" 可以由 "apple" "pen" "apple" 拼接成。注意,你可以重复使用字典中的单词。
示例 3:
输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
输出: false
提示:
1 <= s.length <= 300
1 <= wordDict.length <= 1000
1 <= wordDict[i].length <= 20
s
和wordDict[i]
仅由小写英文字母组成wordDict
中的所有字符串 互不相同
思路
视频讲解:LeetCode:139.单词拆分
代码随想录:139.单词拆分
单词 => 物品,字符串 => 背包,单词可以重复使用说明是完全背包问题。
动态规划五部曲:
- 确定dp数组以及下标的含义:dp数组定义为布尔数组,
dp[i]
表示字符串长度为 i 时能否拆分为字典中出现的单词。 - 确定递推公式:定义当前遍历到的单词为 str,如果
dp[i - str.length()] == true
,且 str 与与字符串中对应的子串相等,dp[i] = true
- 数组初始化:
dp[0] = true
,其余元素定义为 0。 - 确定遍历顺序:本题求的是排列,因此外层 for 循环遍历背包,内层 for 循环遍历物品,由于是完全背包,使用顺序遍历。
- 举例推导:
题解
独立题解:
java">class Solution {public boolean wordBreak(String s, List<String> wordDict) {boolean[] dp = new boolean[s.length() + 1];dp[0] = true;for (int i = 0; i < dp.length; i++) {for (int j = 0; j < wordDict.size(); j++) {String str = wordDict.get(j);int len = str.length();if (i - len >= 0 && s.substring(i - len, i).equals(str) && dp[i - len]) {dp[i] = true;}}}return dp[s.length()];}
}
参考题解:
java">class Solution {public boolean wordBreak(String s, List<String> wordDict) {HashSet<String> set = new HashSet<>(wordDict);boolean[] valid = new boolean[s.length() + 1];valid[0] = true;for (int i = 1; i <= s.length(); i++) {for (int j = 0; j < i && !valid[i]; j++) {if (set.contains(s.substring(j, i)) && valid[j]) {valid[i] = true;}}}return valid[s.length()];}
}
多重背包理论基础
题目
56. 携带矿石资源(第八期模拟笔试)
题目描述:
你是一名宇航员,即将前往一个遥远的行星。在这个行星上,有许多不同类型的矿石资源,每种矿石都有不同的重要性和价值。你需要选择哪些矿石带回地球,但你的宇航舱有一定的容量限制。
给定一个宇航舱,最大容量为 C。现在有 N 种不同类型的矿石,每种矿石有一个重量 w[i],一个价值 v[i],以及最多 k[i] 个可用。不同类型的矿石在地球上的市场价值不同。你需要计算如何在不超过宇航舱容量的情况下,最大化你所能获取的总价值。
输入描述:
输入共包括四行,第一行包含两个整数 C 和 N,分别表示宇航舱的容量和矿石的种类数量。
接下来的三行,每行包含 N 个正整数。具体如下:
第二行包含 N 个整数,表示 N 种矿石的重量。
第三行包含 N 个整数,表示 N 种矿石的价格。
第四行包含 N 个整数,表示 N 种矿石的可用数量上限。
输出描述:
输出一个整数,代表获取的最大价值。
输入示例:
10 3
1 3 4
15 20 30
2 3 2
输出示例:
90
提示信息:
数据范围:
1 <= C <= 10000;
1 <= N <= 10000;
1 <= w[i], v[i], k[i] <= 10000;
思路
代码随想录:多重背包理论基础
多重背包问题可以拆解为01背包,在最里层再添加一个 for 循环遍历每一种商品的数量。
题解
java">import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);/*** bagWeight:背包容量* n:物品种类*/int bagWeight, n;//获取用户输入数据,中间用空格隔开,回车键换行bagWeight = sc.nextInt();n = sc.nextInt();int[] weight = new int[n];int[] value = new int[n];int[] nums = new int[n];for (int i = 0; i < n; i++) weight[i] = sc.nextInt();for (int i = 0; i < n; i++) value[i] = sc.nextInt();for (int i = 0; i < n; i++) nums[i] = sc.nextInt();int[] dp = new int[bagWeight + 1];//先遍历物品再遍历背包,作为01背包处理for (int i = 0; i < n; i++) {for (int j = bagWeight; j >= weight[i]; j--) {//遍历每种物品的个数for (int k = 1; k <= nums[i] && (j - k * weight[i]) >= 0; k++) {dp[j] = Math.max(dp[j], dp[j - k * weight[i]] + k * value[i]);}}}System.out.println(dp[bagWeight]);}
}