代码随想录算法训练营第三十八天 | 322-零钱兑换、279-完全平方数、139-单词拆分
LeetCode322 零钱兑换
题目链接：https://leetcode.cn/problems/coin-change/description/
文章讲解：https://programmercarl.com/0322.零钱兑换.html
视频讲解：https://www.bilibili.com/video/BV14K411R7yv/?vd_source=b989f2b109eb3b17e8178154a7de7a51
完全背包问题，动规五部曲：
- 确定dp数组以及下标的含义
dp[j]表示容量为j的背包装满最少需要dp[j]个物品
- 确定递推公式
不放物品i：dp[j] = dp[j]
放物品i：dp[j] = dp[j-coins[i]] + 1
状态转移方程为dp[j] = Math.min(dp[j]，dp[j-coins[i]] + 1)
- dp数组如何初始化
dp[0] = 0，考虑到递推公式取最小值，其他非零下标应初始化为最大值
- 确定遍历顺序
外层for顺序遍历物品，内层循环遍历背包，求的是组合数
特别的，内层遍历背包时，当遇到dp[j-coins[i]]为初始值时，说明它还没有方法塞满，此时不进入状态转移方程，继续往下遍历
- 举例推导dp数组
class Solution {public int coinChange(int[] coins, int amount) {int[] dp = new int[amount + 1];dp[0] = 0;for(int j = 1; j <= amount; j++){dp[j] = Integer.MAX_VALUE;}for(int i = 0; i < coins.length; i++){for(int j = coins[i]; j <= amount; j++){if(dp[j-coins[i]] != Integer.MAX_VALUE){dp[j] = Math.min(dp[j], dp[j-coins[i]] + 1);}}}if(dp[amount] == Integer.MAX_VALUE){return -1;}return dp[amount];}
}
LeetCode279 完全平方数
题目链接：https://leetcode.cn/problems/perfect-squares/description/
文章讲解：https://programmercarl.com/0279.完全平方数.html
视频讲解：https://www.bilibili.com/video/BV12P411T7Br/?vd_source=b989f2b109eb3b17e8178154a7de7a51
完全背包问题，动规五部曲：
- 确定dp数组以及下标的含义
dp[j]表示容量为j的背包装满最少需要dp[j]个物品
- 确定递推公式
不放物品i：dp[j] = dp[j]
放物品i：dp[j] = dp[j-nums[i]] + 1
状态转移方程为dp[j] = Math.min(dp[j]，dp[j-nums[i]] + 1)
- dp数组如何初始化
dp[0] = 0，考虑到递推公式取最小值，其他非零下标应初始化为最大值
- 确定遍历顺序
外层for顺序遍历物品，内层循环遍历背包，求的是组合数
特别的，内层遍历背包时，当遇到dp[j-nums[i]]为初始值时，说明它还没有方法塞满，此时不进入状态转移方程，继续往下遍历
- 举例推导dp数组
class Solution {public int numSquares(int n) {int[] dp = new int[n+1];dp[0] = 0;for(int j = 1; j <= n; j++){dp[j] = Integer.MAX_VALUE;}for(int i = 0; i*i <= n; i++){for(int j = i*i; j <= n; j++){if(dp[j - i*i] != Integer.MAX_VALUE){dp[j] = Math.min(dp[j], dp[j - i*i] + 1);}}}return dp[n];}
}
LeetCode139 单词拆分
题目链接：https://leetcode.cn/problems/word-break/description/
文章讲解：https://programmercarl.com/0139.单词拆分.html
视频讲解：https://www.bilibili.com/video/BV1pd4y147Rh/?vd_source=b989f2b109eb3b17e8178154a7de7a51
完全背包问题，动规五部曲：
- 确定dp数组以及下标的含义
单词就是物品，字符串s就是背包，单词能否组成字符串s，就是物品能否把背包装满；拆分时可以重复使用单词，就是可以重复使用物品，属于完全背包问题
字符串的长度为i，若字符串s[0，i]的字符串能被单词组成，则dp[i] = true
- 确定递推公式
如果s[j，i]可以被单词组成，且dp[j] = true，那么dp[i] = true
- dp数组如何初始化
dp[0] = true，作为递推公式的基础，无实际意义，其他非零下标初始化为false
- 确定遍历顺序
外层for顺序遍历背包，内层for顺序遍历物品，求的是排列数
- 举例推导dp数组
class Solution {public boolean wordBreak(String s, List<String> wordDict) {HashSet<String> words = new HashSet<>(wordDict);boolean[] dp = new boolean[s.length()+1];dp[0] = true;for(int j = 1; j <= s.length(); j++){for(int i = 0; i < j; i++){String str = s.substring(i, j);if(words.contains(str) && dp[i]){dp[j] = true;break;}}}return dp[s.length()];}
}