算法学习——LeetCode力扣动态规划篇4
377. 组合总和 Ⅳ
377. 组合总和 Ⅳ - 力扣（LeetCode）
描述
给你一个由 不同 整数组成的数组 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
代码解析
动态规划
和518零钱兑换II 的区别是
- 518零钱兑换II 是组合数，有多少种组合
- 此题是找排序数
如果求组合数就是外层for循环遍历物品，内层for遍历背包。
如果求排列数就是外层for遍历背包，内层for循环遍历物品。
class Solution {
public:
int combinationSum4(vector<int>& nums, int target) {
vector<int> dp(target+1 ,0);
dp[0] = 1;
for(int j=0 ; j<=target ;j++)
{
for(int i=0 ; i<nums.size() ;i++)
{
if(j>=nums[i] && dp[j] < INT_MAX - dp[j-nums[i]])
{
dp[j] += dp[j-nums[i]];
}
else dp[j] = dp[j];
}
}
return dp[target];
}
};
C++测试用例有两个数相加超过int的数据，所以需要在if里加上dp[i] < INT_MAX - dp[i - num]。
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
代码解析
动态规划
dp[j]：凑足总额为j所需钱币的最少个数为dp[j]
得到dp[j]，只有一个来源，dp[j - coins[i]]。
凑足总额为j - coins[i]的最少个数为dp[j - coins[i]]，那么只需要加上一个钱币coins[i]即dp[j - coins[i]] + 1就是dp[j]
递推公式：dp[j] = min(dp[j - coins[i]] + 1, dp[j]);
首先凑足总金额为0所需钱币的个数一定是0，那么dp[0] = 0;
class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
vector<int> dp(amount+1 ,INT_MAX);
dp[0]=0;
for(int i=0 ; i<coins.size() ; i++)
{
for(int j=0 ; j<=amount ;j++)
{
if(j>=coins[i] && dp[j-coins[i]] != INT_MAX)
{
dp[j] = min( dp[j], dp[j-coins[i]] + 1);
}
}
}
if(dp[amount]==INT_MAX) 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
代码解析
动态规划
和322零钱兑换完全一致
自己构建完全平方数组，作为价格数组
找到刚好装满背包，但使用金币数量最少的金币数
class Solution {
public:
int numSquares(int n) {
vector<int> sqrt_num;
vector<int> dp(n+1,INT_MAX);
int tmp = 1;
while( pow(tmp,2) <= n )
{
sqrt_num.push_back(pow(tmp,2));
tmp++;
}
dp[0]=0;
for(int i=0 ;i<sqrt_num.size();i++)
{
for(int j=sqrt_num[i] ; j<=n ;j++)
dp[j] = min(dp[j] , dp[j-sqrt_num[i]]+1 );
}
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 中的所有字符串 互不相同
代码解析
动态规划
单词就是物品，字符串s就是背包，单词能否组成字符串s，就是问物品能不能把背包装满。
拆分时可以重复使用字典中的单词，说明就是一个完全背包！
dp[i] : 字符串长度为i的话，dp[i]为true，表示可以拆分为一个或多个在字典中出现的单词。
dp[0]初始为true完全就是为了推导公式。
下标非0的dp[i]初始化为false，只要没有被覆盖说明都是不可拆分为一个或多个在字典中出现的单词。
dp[j]=true 来自于 dp[i]=true + 字串s(i，j-i)可以在字典中找到。
例如输入“leetcode” ，dp[ 0 ] 初始化为1 ，
dp[ 4 ] = 1 , 因为 dp[ 0 ] =1 ，字串 s（ 0 ， 4 - 0）即”leet“ 可以在字典找到
dp[ 8 ] = 1 , 因为 dp[ 4 ] =1 ，字串 s（ 4 ， 8 - 4）即”code“ 可以在字典找到
class Solution {
public:
bool wordBreak(string s, vector<string>& wordDict) {
vector<bool> dp(s.size()+1 ,false);
unordered_set<string> wordSet(wordDict.begin(), wordDict.end());
dp[0] = true;
// dp[j]=true 来自于 dp[i]=true + 字串s(i，j-i)可以在字典中找到。
for(int j = 1 ; j<=s.size() ; j++)//背包尺寸
{
for(int i = 0 ; i < j ;i++ )//字串长度
{
string word = s.substr( i , j-i );
if(wordSet.find(word) != wordSet.end() && dp[i]==true )
dp[j] = true;
}
}
// for(auto it:dp) cout<<it<<' ';
return dp[s.size()];
}
};
