代码随想录算法训练营第37天| 139.单词拆分；279.完全平方数；322. 零钱兑换
第九章 动态规划part06
322. 零钱兑换
如果求组合数就是外层for循环遍历物品，内层for遍历背包。
如果求排列数就是外层for遍历背包，内层for循环遍历物品。
这句话结合本题 大家要好好理解。
视频讲解：https://www.bilibili.com/video/BV14K411R7yv
class Solution {
public int coinChange(int[] coins, int amount) {
int max = Integer.MAX_VALUE;
int[] dp = new int[amount + 1];
//初始化dp数组为最大值
for (int j = 0; j < dp.length; j++) {
dp[j] = max;
}
//当金额为0时需要的硬币数目为0
dp[0] = 0;
for (int i = 0; i < coins.length; i++) {
//正序遍历：完全背包每个硬币可以选择多次
for (int j = coins[i]; j <= amount; j++) {
//只有dp[j-coins[i]]不是初始最大值时，该位才有选择的必要
if (dp[j - coins[i]] != max) {
//选择硬币数目最小的情况
dp[j] = Math.min(dp[j], dp[j - coins[i]] + 1);
}
}
}
return dp[amount] == max ? -1 : dp[amount];
}
}
279.完全平方数
本题 和 322. 零钱兑换 基本是一样的，大家先自己尝试做一做
视频讲解：https://www.bilibili.com/video/BV12P411T7Br
https://programmercarl.com/0279.%E5%AE%8C%E5%85%A8%E5%B9%B3%E6%96%B9%E6%95%B0.html
class Solution {
// 版本一，先遍历物品, 再遍历背包
public int numSquares(int n) {
int max = Integer.MAX_VALUE;
int[] dp = new int[n + 1];
//初始化
for (int j = 0; j <= n; j++) {
dp[j] = max;
}
//如果不想要寫for-loop填充數組的話，也可以用JAVA內建的Arrays.fill()函數。
//Arrays.fill(dp, Integer.MAX_VALUE);
//当和为0时，组合的个数为0
dp[0] = 0;
// 遍历物品
for (int i = 1; i * i <= n; i++) {
// 遍历背包
for (int j = i * i; j <= n; j++) {
//if (dp[j - i * i] != max) {
dp[j] = Math.min(dp[j], dp[j - i * i] + 1);
//}
//不需要這個if statement，因爲在完全平方數這一題不會有"湊不成"的狀況發生（ 一定可以用"1"來組成任何一個n），故comment掉這個if statement。
}
}
return dp[n];
}
}
class Solution {
// 版本二， 先遍历背包, 再遍历物品
public int numSquares(int n) {
int max = Integer.MAX_VALUE;
int[] dp = new int[n + 1];
// 初始化
for (int j = 0; j <= n; j++) {
dp[j] = max;
}
// 当和为0时，组合的个数为0
dp[0] = 0;
// 遍历背包
for (int j = 1; j <= n; j++) {
// 遍历物品
for (int i = 1; i * i <= j; i++) {
dp[j] = Math.min(dp[j], dp[j - i * i] + 1);
}
}
return dp[n];
}
}
139.单词拆分
视频讲解：https://www.bilibili.com/video/BV1pd4y147Rh
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()];
}
}
// 另一种思路的背包算法
class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
boolean[] dp = new boolean[s.length() + 1];
dp[0] = true;
for (int i = 1; i <= s.length(); i++) {
for (String word : wordDict) {
int len = word.length();
if (i >= len && dp[i - len] && word.equals(s.substring(i - len, i))) {
dp[i] = true;
break;
}
}
}
return dp[s.length()];
}
}
// 回溯法+记忆化
class Solution {
private Set<String> set;
private int[] memo;
public boolean wordBreak(String s, List<String> wordDict) {
memo = new int[s.length()];
set = new HashSet<>(wordDict);
return backtracking(s, 0);
}
public boolean backtracking(String s, int startIndex) {
// System.out.println(startIndex);
if (startIndex == s.length()) {
return true;
}
if (memo[startIndex] == -1) {
return false;
}
for (int i = startIndex; i < s.length(); i++) {
String sub = s.substring(startIndex, i + 1);
// 拆分出来的单词无法匹配
if (!set.contains(sub)) {
continue;
}
boolean res = backtracking(s, i + 1);
if (res) return true;
}
// 这里是关键，找遍了startIndex~s.length()也没能完全匹配，标记从startIndex开始不能找到
memo[startIndex] = -1;
return false;
}
}
关于多重背包，你该了解这些！
https://programmercarl.com/%E8%83%8C%E5%8C%85%E9%97%AE%E9%A2%98%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80%E5%A4%9A%E9%87%8D%E8%83%8C%E5%8C%85.html
背包问题总结篇！
https://programmercarl.com/%E8%83%8C%E5%8C%85%E6%80%BB%E7%BB%93%E7%AF%87.html
原文地址：https://blog.csdn.net/weixin_44647325/article/details/142782405
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！