377 组合总和Ⅱ
题目
给你一个由 不同 整数组成的数组
nums
,和一个目标整数target
。请你从nums
中找出并返回总和为target
的元素组合的个数。 题目数据保证答案符合 32 位整数范围。 示例 1: 输入:nums = [1,2,3], target = 4 输出:7 解释: 所有可能的组合为: (1, 1, 1, 1) (1, 1, 2) (1, 2, 1) (1, 3) (2, 1, 1) (2, 2) (3, 1) 请注意,顺序不同的序列被视作不同的组合。 示例 2: 输入:nums = [9], target = 3 输出:0 提示:
1 <= nums.length <= 200
1 <= nums[i] <= 1000
nums
中的所有元素 互不相同1 <= target <= 1000
进阶:如果给定的数组中含有负数会发生什么?问题会产生何种变化?如果允许负数出现,需要向题目中添加哪些限制条件?
思路
题目中说到:从 nums 中找出并返回总和为 target 的元素组合的个数。
但是后面又紧跟着说顺序不同的作为不同的组合。 那么本题就不能看成单纯的组合数 ,而是排列。因为排列对于顺序有要求, 所以需要按照排列的思维去思考同时还需要有动态规划的思考。 这就是这道题难的地方。
按照动规的思路dp[i]
: 表示总和为i的组合的个数为dp[i]
还有需要注意的就是遍历的顺序, 一般来说对于背包问题:
**求组合是外层遍历物品,内层遍历背包。 **
求排列是外层遍历背包,内层遍历物品。
所以,本题我们也是采用这种遍历方式进行。
实现
代码语言:javascript复制class Solution {
public int combinationSum4(int[] nums, int target) {
//如果求组合数就是外层for循环遍历物品,内层for遍历背包。
// 如果求排列数就是外层for遍历背包,内层for循环遍历物品。
int []dp = new int[target 1];
dp[0] = 1;
//外层遍历背包
for(int j = 0; j <= target;j ){
//内层遍历物品
for(int i =0 ;i < nums.length;i ){
//如果被当前背包的容量 >= 物品的重量, 那么就进行递推。 否则就遍历下一个数
if( j >= nums[i] ){
//求组合数使用 = 求最大值/最小值 使用max/min
dp[j] = dp[j-nums[i]];
}
}
}
return dp[target];
}
}
322 零钱总换
题目
给你一个整数数组
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
思路
本题和我们之前做的零钱总换(地址: https://wclspace.xyz/post/4ee41ff3.html#518-零钱总换)是一个类型的题, 上一道这个题是要求返回凑成总金额的组合数, 而本题是返回可以凑成总金额所需的最少的硬币个数
所以这两道题在递推公式上略有不同。
dp[i]:
表示 可以凑成总金额 i 所需的 最少的硬币个数为dp[i]
这道题对于遍历的位次顺序要求就没那么高了, 先遍历背包或者物品都行 ,这里我用先遍历物品(习惯)。同时, 因为对于数组中的银币的数量是无限制的, 所以我们可以一直使用同一个, 所以在内层遍历背包的时候需要正序遍历, 这样就可以保证同一个硬币被多次使用了。
注意: 因为要获取最少的硬币个数 ,所以在初始化dp数组的时候需要将其赋予最大值, 这样才能再每次递推的时候获取最小值(也就是最少使用硬币个数)
对于dp[0]
的初始化,这里给dp[0] = 0
,按照题意总金额为 0的个数也是 0 。 所以可以赋值为0 , 至于其他的, 我们需要赋值为最大值 ,原因上面有说
实现
代码语言:javascript复制class Solution {
public int coinChange(int[] coins, int amount) {
//题目要求 : 返回可以凑成总金额所需的 最少的硬币个数
int []dp = new int[amount 1];
//dp[i] 表示 凑成总金额为i所需要的最少硬币数为 dp[i]
//需要计算最大的硬币面值
for(int i = 0;i < dp.length; i ){
dp[i] = Integer.MAX_VALUE;
}
//初始化dp[0] = 0 if amount == 0 then dp[0] = 0
dp[0] = 0;
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);
}
}
}
return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
}
}
279 完全平方数
题目
给你一个整数
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
思路
题中要求: 返回和为 n的完全平方数的最少数量
所以**dp[i]:
可以表示 和为 i 的完全平方数的最少数量是dp[i]
**
遍历顺序还是使用先物品 后背包的方式, 如果物品的重量 > 背包的容量。 那么就直接continue, 否则就进行递推公式
代码语言:javascript复制for(int i= 1; i*i <= n; i ){
for(int j = i*i; j<= n; j )
}
因为本题需要的是最数量, 所以我们在初始化dp[i]
的时候, 需要将其赋值为MAX_VALUE
, 这样才能实现min(dp[j],dp[j-i*i] 1)
的时候取最小值。 同时对于dp[0] =0
因为 和为 0 的完全平方数最少数量本来就是 0
实现
代码语言:javascript复制class Solution {
public int numSquares(int n) {
int []dp = new int[n 1];
//dp[i]: dp数组的含义是 和为整数i的 完全平方数最少数量为dp[i]
for(int i =0 ;i <= n; i ){
dp[i] = Integer.MAX_VALUE;
}
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], dp[j- i*i] 1);
}
}
return dp[n];
}
}
139 单词拆分
题目
给你一个字符串
s
和一个字符串列表wordDict
作为字典。请你判断是否可以利用字典中出现的单词拼接出s
。 注意:不要求字典中出现的单词全部都使用,并且字典中的单词可以重复使用。 示例 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
中的所有字符串 互不相同
思路
二刷fail
因为题目中混合字符串, 所以一时没有想出来字符串的拆分和dp[]
数组怎么建立联系, 如何知道s中是否含有wordDict的内容, 刚开始想到的是用集合来contains判断, 但是这样会导致时间复杂度极高, 比暴力还爆力,根本不可行,所以就没有ac下来。
先不考虑如何判断s中是否存在wordDict中的词, 先按照动态规划的思路将这道题理顺。
既然是看 wordDict是否在s中, 那么就把s看作背包, 看wordDict中的内容能否将其装满, 能那就返回true ,不能就是false ,暂时就这么简单的思考。
接下来按照动规五部曲。 dp[i]
:字符串长度为i, dp[i] = true
,表示可以拆分为一个或多个在字典中出现的单词。
初始化dp[0] = true
。因为dp[i]
的状态依靠 dp[j]
是否为true,那么dp[0]
就是递推的根基,dp[0]
一定要为true,否则递推下去后面都都是false了。
实现
代码语言:javascript复制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 str: wordDict){
int len = str.length();
//判断是否满足条件
//1. len<=i
//2. s.substring(i-len, i) == str
//3. dp的递推公式中的dp[i-len] == true ,需要判断上一个循环是否满足条件
if(i>= len && dp[i-len] && str.equals(s.substring(i-len,i))){
dp[i] = true;
break;
}
}
}
return dp[s.length()];
}
}