518.零钱兑换II
518. 零钱兑换 II - 力扣（LeetCode）
1
2
3
4
5
6
7
8
9
10
11
12
13
| 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];
}
};
|
虽然题简单，但是遍历顺序须仔细琢磨
因为纯完全背包求得装满背包的最大价值是多少，和凑成总和的元素有没有顺序没关系，即：有顺序也行，没有顺序也行。
而本题要求凑成总和的组合数，元素之间明确要求没有顺序。
所以纯完全背包是能凑成总和就行，不用管怎么凑的。
本题是求凑出来的方案个数，且每个方案个数是为组合数。
那么本题，两个for循环的先后顺序可就有说法了。
先来看 外层for循环遍历物品（钱币），内层for遍历背包（金钱总额）的情况。
代码如下：
1
2
3
4
5
| for (int i = 0; i < coins.size(); i++) {
for (int j = coins[i]; j <= amount; j++) {
dp[j] += dp[j - coins[i]];
}
}
|
假设：coins[0] = 1，coins[1] = 5。
那么就是先把1加入计算，然后再把5加入计算，得到的方法数量只有{1, 5}这种情况。而不会出现{5, 1}的情况。
所以这种遍历顺序中dp[j]里计算的是组合数！
如果把两个for交换顺序，代码如下：
1
2
3
4
5
| for (int j = 0; j <= amount; j++) {
for (int i = 0; i < coins.size(); i++) {
if (j - coins[i] >= 0) dp[j] += dp[j - coins[i]];
}
}
|
背包容量的每一个值，都是经过 1 和 5 的计算，包含了{1, 5} 和 {5, 1}两种情况。
此时dp[j]里算出来的就是排列数！
377. 组合总和 Ⅳ
377. 组合总和 Ⅳ - 力扣（LeetCode）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public:
int combinationSum4(vector<int>& coins, int amount) {
vector<int> dp(amount + 1, 0);
dp[0] = 1;
for (int i = 0; i <= amount; i++) {
for (int j = 0; j < coins.size(); j++) {
if (i - coins[j] >= 0&&dp[i] < INT_MAX - dp[i-coins[j]])
dp[i] += dp[i - coins[j]];
}
}
return dp[amount];
}
};
|
总结：
如果求组合数就是外层for循环遍历物品，内层for遍历背包。
如果求排列数就是外层for遍历背包，内层for循环遍历物品。
70. 爬楼梯（进阶版）
57. 爬楼梯（第八期模拟笔试） (kamacoder.com)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| #include <iostream>
#include <vector>
using namespace std;
int main(){
int n,m;
cin>>n>>m;
vector<int> dp(n+1,0);
dp[0]=1;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(i-j>=0)
dp[i]+=dp[i-j];
cout<<dp[n];
}
|
322. 零钱兑换
322. 零钱兑换 - 力扣（LeetCode）
定义：：凑足总额为j所需钱币的最少个数为
递推公式：
初始化：
遍历顺序：都行
1
2
3
4
| for (int i = 0; i < coins.size(); i++)
for (int j = coins[i]; j <= amount; j++)
if (dp[j - coins[i]] != INT_MAX)
dp[j] = min(dp[j - coins[i]] + 1, dp[j]);
|
1
2
3
4
| for (int i = 1; i <= amount; i++)
for (int j = 0; j < coins.size(); j++)
if (i - coins[j] >= 0 && dp[i - coins[j]] != INT_MAX )
dp[i] = min(dp[i - coins[j]] + 1, dp[i]);
|
完整代码如下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| 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 = coins[i]; j <= amount; j++) {
if (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）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution {
public:
int numSquares(int n) {
vector<int> dp(n + 1, INT_MAX);
dp[0] = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j * j <= i; j++) {
dp[i] = min(dp[i], dp[i - j * j] + 1);
}
}
return dp[n];
}
};
|
139.单词拆分
139. 单词拆分 - 力扣（LeetCode）
没思路
定义：dp[i] : 字符串长度为i的话，dp[i]为true，表示可以拆分为一个或多个在字典中出现的单词。
递推公式：如果确定dp[j] 是true，且 [j, i] 这个区间的子串出现在字典里，那么dp[i]一定是true。（j < i ）。所以递推公式是 if([j, i] 这个区间的子串出现在字典里 && dp[j]是true) 那么 dp[i] = true。
初始化：dp[0]=true，下标非0的dp[i]初始化为false
遍历顺序：有序！所以先背包后物品！
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public:
bool wordBreak(string s, vector<string>& wordDict) {
unordered_set<string> wordset(wordDict.begin(), wordDict.end());
vector<bool> dp(s.size() + 1, false);
dp[0] = 1;
for (int i = 0; i <= s.size(); i++) {
for (int j = 0; j < i; j++) {
string sub = s.substr(j, i - j);
if (wordset.find(sub) != wordset.end() && dp[j])
dp[i] = true;
}
}
return dp[s.size()];
}
};
|
198.打家劫舍
198. 打家劫舍 - 力扣（LeetCode）
定义：dp[i]：考虑下标i（包括i）以内的房屋，最多可以偷窃的金额为dp[i]。
递推公式：dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);
初始化：dp[0]=nums[0],dp[1]=max(nums[0],nums[1]);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public:
int rob(vector<int>& nums) {
if (nums.size() == 0)
return 0;
if (nums.size() == 1)
return nums[0];
vector<int> dp(nums.size() + 1, 0);
dp[0] = nums[0];
dp[1] = max(nums[0], nums[1]);
for (int i = 2; i < nums.size(); i++) {
dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);
}
return dp[nums.size() - 1];
}
};
|
213.打家劫舍II
213. 打家劫舍 II - 力扣（LeetCode）
变化为环状，需要单独考虑首尾元素
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution {
public:
int rob1(vector<int> nums, int start, int end) {
if (end == start) return nums[start];
vector<int> dp(nums.size(), 0);
dp[start] = nums[start];
dp[start+1] = max(nums[start], nums[start + 1]);
for (int i = start + 2; i <= end; i++) {
dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);
}
return dp[end];
}
int rob(vector<int>& nums) {
if (nums.size() == 0)
return 0;
if (nums.size() == 1)
return nums[0];
int res1 = rob1(nums, 0, nums.size() - 2);
int res2 = rob1(nums, 1, nums.size() - 1);
return max(res1, res2);
}
};
|
337.打家劫舍 III
337. 打家劫舍 III - 力扣（LeetCode）
