代码随想录算法训练营Day43 | 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] <= 2³¹ - 1
0 <= amount <= 10⁴

思路

代码随想录：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。
确定遍历顺序：本题求的是硬币最小个数，可以选择外层遍历物品内层遍历背包（反过来也可以），由于是完全背包类型，所以选择顺序遍历。
举例推导：

322.零钱兑换

题解

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 <= 10⁴

思路

代码随想录：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 循环遍历物品，由于是完全背包，使用顺序遍历。
举例推导：

139.单词拆分

题解

独立题解：

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 种矿石的可用数量上限。

输出描述：

输出一个整数，代表获取的最大价值。

输入示例：

输出示例：

提示信息：

数据范围：
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]);}
}