第四十四天打卡
零錢兌換 II
- 零錢兌換 II
中等
1K
相關(guān)企業(yè)
給你一個整數(shù)數(shù)組 coins 表示不同面額的硬幣，另給一個整數(shù) amount 表示總金額。
請你計算并返回可以湊成總金額的硬幣組合數(shù)。如果任何硬幣組合都無法湊出總金額，返回 0 。
假設(shè)每一種面額的硬幣有無限個。
題目數(shù)據(jù)保證結(jié)果符合 32 位帶符號整數(shù)。
示例 1：
輸入：amount = 5, coins = [1, 2, 5]
輸出：4
解釋：有四種方式可以湊成總金額：
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1
示例 2：
輸入：amount = 3, coins = [2]
輸出：0
解釋：只用面額 2 的硬幣不能湊成總金額 3 。
示例 3：
輸入：amount = 10, coins = [10]
輸出：1
提示：
1 <= coins.length <= 300
1 <= coins[i] <= 5000
coins 中的所有值 互不相同
0 <= amount <= 5000
class Solution {
public:
int change(int amount, vector<int>& coins) {
vector<int> dp(amount+1,0);
dp[0]=1;
for(int i=0;i<coins.size();i++)
{
for(int j=coins[i];j<=amount;j++)
{
dp[j]+=dp[j-coins[i]];
}
}
return dp[amount];
}
};
組合總和 Ⅳ
- 組合總和 Ⅳ
中等
779
相關(guān)企業(yè)
給你一個由 不同 整數(shù)組成的數(shù)組 nums ，和一個目標(biāo)整數(shù) target 。請你從 nums 中找出并返回總和為 target 的元素組合的個數(shù)。
題目數(shù)據(jù)保證答案符合 32 位整數(shù)范圍。
示例 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文章來源：http://www.zghlxwxcb.cn/news/detail-438695.html
進(jìn)階：如果給定的數(shù)組中含有負(fù)數(shù)會發(fā)生什么？問題會產(chǎn)生何種變化？如果允許負(fù)數(shù)出現(xiàn)，需要向題目中添加哪些限制條件？文章來源地址http://www.zghlxwxcb.cn/news/detail-438695.html
class Solution {
public:
int combinationSum4(vector<int>& nums, int target) {
vector<int> dp(target+1,0);
dp[0]=1;
for (int i = 0; i <= target; i++)
{
for(int j=0;j<nums.size();j++)
{
if(i-nums[j]>=0&&dp[i]<INT_MAX-dp[i-nums[j]])
{
dp[i]+=dp[i-nums[j]];
}
}
}
return dp[target];
}
};
到了這里，關(guān)于第四十四天打卡的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
