# 1520. Maximum Number of Non-Overlapping Substrings Hard 可转化为01背包

#### 题目

https://leetcode.com/contest/weekly-contest-198/problems/maximum-number-of-non-overlapping-substrings/
Given a string s of lowercase letters, you need to find the maximum number of non-empty substrings of s that meet the following conditions:

The substrings do not overlap, that is for any two substrings s[i..j] and s[k..l], either j < k or i > l is true.
A substring that contains a certain character c must also contain all occurrences of c.
Find the maximum number of substrings that meet the above conditions. If there are multiple solutions with the same number of substrings, return the one with minimum total length. It can be shown that there exists a unique solution of minimum total length.

Notice that you can return the substrings in any order.

Example 1:

Output: [“e”,”f”,”ccc”]
Explanation: The following are all the possible substrings that meet the conditions:
[
“ef”,
“e”,
“f”,
“ccc”,
]
If we choose the first string, we cannot choose anything else and we’d get only 1. If we choose “adefadda”, we are left with “ccc” which is the only one that doesn’t overlap, thus obtaining 2 substrings. Notice also, that it’s not optimal to choose “ef” since it can be split into two. Therefore, the optimal way is to choose [“e”,”f”,”ccc”] which gives us 3 substrings. No other solution of the same number of substrings exist.
Example 2:

Input: s = “abbaccd”
Output: [“d”,”bb”,”cc”]
Explanation: Notice that while the set of substrings [“d”,”abba”,”cc”] also has length 3, it’s considered incorrect since it has larger total length.

Constraints:

1 <= s.length <= 10^5
s contains only lowercase English letters.

#### 思路

1. 找到所有字母的最小下标和最大下标
2. 针对每一个字母将游标从其最小下标开始遍历，针对每一个字母判断如果无法包含在当前区间内，则该字母无法作为一个合法字符串的开头；否则更新 end 的值，该方法是贪心的得到的都是最短的合法字串

#### 源码

``````class Solution {
public:
static bool cmp(vector<int> a,vector<int> b){
return a[0] > b[0];
}
vector<string> maxNumOfSubstrings(string s) {
vector<vector<int>> bg(26),valid;
for(int i = 0;i < s.length();++i){
bg[s[i]-'a'].push_back(i);
}
for(int i = 0;i < 26;++i){
if(bg[i].size() < 1) continue;
int end = bg[i].back();
int idx = bg[i][0];
bool f = true;
for(;idx!=end;idx++){
//cout << idx<<endl;
if(s[idx]=='a'+i)continue;
if(bg[s[idx]-'a'][0]<bg[i][0]){
f = false;
break;
}
end = max(end,bg[s[idx]-'a'].back());
}
//合法
if(f){
vector<int> pair;
pair.push_back(bg[i][0]);
pair.push_back(end);
valid.push_back(pair);
}
}
//输出合法字符串长度
sort(valid.begin(),valid.end(),cmp);
//背包问题
vector<long> dp(s.length()+1,0);
vector<vector<int>> path(valid.size()+1,vector<int>(s.length()+1,0)),se(valid.size()+1,vector<int>(s.length()+1,0));
for(int i = 0;i < valid.size();++i){
//cout <<"i = "<<i<<endl;
int len = valid[i].back()-valid[i][0]+1;
int start = valid[i][0];
int end = valid[i].back();
//cout <<"Start = "<<start<<endl;
for(int j = 0;j <= s.length();++j){
if(j>start){
path[i][j]=i==0?0:path[i-1][j];
continue;
}
if(dp[j]>dp[end+1]+1){
//不选
dp[j] = dp[j];
path[i][j] = i==0?0:path[i-1][j];
se[i][j]=0;
}else if(dp[j]<dp[end+1]+1){
//选
dp[j] = dp[end+1]+1;
path[i][j] = i==0?len:path[i-1][end+1]+len;
se[i][j]=1;
}else{
if(path[i-1][j]<path[i-1][end+1]+len){
//不选
dp[j] = dp[j];
path[i][j] = i==0?0:path[i-1][j];
}else{
//选
dp[j] = dp[end+1]+1;
path[i][j] = i==0?len:path[i-1][end+1]+len;
se[i][j]=1;
}
}
// dp[j] = max(dp[j],dp[end+1]+1);
//cout <<"path"<<j<<" = "<<path[i][j]<<endl;
}
// cout<<endl;
}
//cout << dp[0]<<endl;
int idx = 0;
vector<string> res;
for(int i = valid.size()-1;i >=0;--i){
int len = valid[i].back()-valid[i][0]+1;
if(se[i][idx]!=0){
string  ss = s.substr(valid[i][0],len);
idx+=len;
// cout << ss<<endl;
res.push_back(ss);
}
}
return res;
}
};
``````

# leetcode 1530. Number of Good Leaf Nodes Pairs LCA 最近公共祖先

#### 题目

https://leetcode.com/problems/number-of-good-leaf-nodes-pairs/
Given the root of a binary tree and an integer distance. A pair of two different leaf nodes of a binary tree is said to be good if the length of the shortest path between them is less than or equal to distance.

Return the number of good leaf node pairs in the tree.

Example 1:

Input: root = [1,2,3,null,4], distance = 3
Output: 1
Explanation: The leaf nodes of the tree are 3 and 4 and the length of the shortest path between them is 3. This is the only good pair.
Example 2:

Input: root = [1,2,3,4,5,6,7], distance = 3
Output: 2
Explanation: The good pairs are [4,5] and [6,7] with shortest path = 2. The pair [4,6] is not good because the length of ther shortest path between them is 4.
Example 3:

Input: root = [7,1,4,6,null,5,3,null,null,null,null,null,2], distance = 3
Output: 1
Explanation: The only good pair is [2,5].
Example 4:

Input: root = [100], distance = 1
Output: 0
Example 5:

Input: root = [1,1,1], distance = 2
Output: 1

Constraints:

The number of nodes in the tree is in the range [1, 2^10].
Each node’s value is between [1, 100].
1 <= distance <= 10

#### 源码

``````/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode() : val(0), left(nullptr), right(nullptr) {}
*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
struct RES{
int cnt = 0;
vector<pair<int,int>> dis;
};
class Solution {
public:
int dd;
int countPairs(TreeNode* root, int distance) {
dd = distance;
RES res =  dfs(root);
return res.cnt;
}
RES dfs(TreeNode* root){
RES res;
if(root == NULL)return res;
if(root->left==NULL&&root->right==NULL)
res.dis.push_back(make_pair(0,1));
RES l = dfs(root->left);
RES r = dfs(root->right);
res.cnt = l.cnt+r.cnt;
for(int i = 0;i < l.dis.size();++i){
for(int j = 0;j < r.dis.size();++j){
pair<int,int> ll = l.dis[i];
pair<int,int> rr = r.dis[j];
// cout << ll.first<<" "<<rr.first<<" d: "<<ll.second<<" "<<rr.second<<endl;
if(ll.first+rr.first+2<=dd){
res.cnt+=ll.second*rr.second;
}
}
}
//  cout << l.cnt<<endl;
//cout << r.cnt<<endl<<endl;
map<int,int> m;
for(auto p:l.dis){
m[p.first]+=p.second;
}
for(auto p:r.dis){
m[p.first]+=p.second;
}
for(auto p:m){
res.dis.push_back(make_pair(p.first+1,p.second));
}
return res;
}
};
``````

discuss 里看见一份代码同样的逻辑后续遍历，人家代码写的就贼优雅

``````/*
https://leetcode.com/problems/number-of-good-leaf-nodes-pairs/submissions/

Idea is to find out the distance of leaf nodes in left and right subtrees
for each of the parent nodes. For a node 'i', if we know the distance of leaf nodes
in its left and right from it, then we can just check if the sum of distance of the leaf nodes
in left and right <= dist limit, that makes it a good pair.

*/

/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode() : val(0), left(nullptr), right(nullptr) {}
*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
// TC: O(n * d * d), d: max distance limit, n: num of nodes
vector<int> postOrder(TreeNode *root, int &distance,
int &good_leaves) {
// dist(i): no. of leaf nodes with dist 'i' from current node
vector<int> dist(distance + 1, 0);
if(!root)
return dist;

// when current is a leaf node, its distance with its parent will be 1
if(!root->left && !root->right) {
dist[1] = 1;
return dist;
}

// find the distance of leaf and right subtree leaf nodes
auto left_dist = postOrder(root->left, distance, good_leaves);
auto right_dist = postOrder(root->right, distance, good_leaves);

// now check the distances between leaf nodes of leaf and right
// subtrees which are under limit
for(int i = 0; i < left_dist.size(); i++)
for(int j = 0; j < right_dist.size(); j++)
if(i + j <= distance) {
good_leaves += (left_dist[i] * right_dist[j]);
}
// Update the distance for parent and include the current node
for(int i = 1; i <= distance; i++) {
// (i-1) distance becomes distance 'i'
dist[i] = left_dist[i-1] + right_dist[i-1];
}

return dist;
}

int countPairs(TreeNode* root, int distance) {
int good_leaves = 0, curr_dist = -1;
postOrder(root, distance, good_leaves);
return good_leaves;
}
};
``````

# leetcode 1537. Get the Maximum Score merge 变体 取模谨慎

#### 题目

https://leetcode.com/contest/weekly-contest-200/problems/get-the-maximum-score/
You are given two sorted arrays of distinct integers nums1 and nums2.

A valid path is defined as follows:

Choose array nums1 or nums2 to traverse (from index-0).
Traverse the current array from left to right.
If you are reading any value that is present in nums1 and nums2 you are allowed to change your path to the other array. (Only one repeated value is considered in the valid path).
Score is defined as the sum of uniques values in a valid path.

Return the maximum score you can obtain of all possible valid paths.

Since the answer may be too large, return it modulo 10^9 + 7.

Example 1:

Input: nums1 = [2,4,5,8,10], nums2 = [4,6,8,9]
Output: 30
Explanation: Valid paths:
[2,4,5,8,10], [2,4,5,8,9], [2,4,6,8,9], [2,4,6,8,10], (starting from nums1)
[4,6,8,9], [4,5,8,10], [4,5,8,9], [4,6,8,10] (starting from nums2)
The maximum is obtained with the path in green [2,4,6,8,10].
Example 2:

Input: nums1 = [1,3,5,7,9], nums2 = [3,5,100]
Output: 109
Explanation: Maximum sum is obtained with the path [1,3,5,100].
Example 3:

Input: nums1 = [1,2,3,4,5], nums2 = [6,7,8,9,10]
Output: 40
Explanation: There are no common elements between nums1 and nums2.
Maximum sum is obtained with the path [6,7,8,9,10].
Example 4:

Input: nums1 = [1,4,5,8,9,11,19], nums2 = [2,3,4,11,12]
Output: 61

Constraints:

1 <= nums1.length <= 10^5
1 <= nums2.length <= 10^5
1 <= nums1[i], nums2[i] <= 10^7
nums1 and nums2 are strictly increasing.

#### 思路

merge sort
i,j 分别为两个 list 的游标，向前移动并累计求和，对于相同值的两个节点，其后可以选择之前的任意一个分支，同一个 list 两个跳转节点间的值可以压缩为一个节点，所以最终将跳转节点位置对齐，便利跳转节点只需要选择两个 list 中值较大的即可

#### 源码

``````class Solution {
public:
int maxSum(vector<int>& nums1, vector<int>& nums2) {
int  i = 0,j = 0;
int mod = 1000000007;
long long res = 0;
long long sum1 = 0,sum2 = 0;
while(i<nums1.size()&&j<nums2.size()){
if(nums1[i]==nums2[j]){
res = (res+max(sum1,sum2)+nums1[i])%mod;
sum1 = sum2 = 0;
i++;
j++;
}else if(nums1[i]<nums2[j]){
sum1=(sum1+nums1[i]);
i++;
}else{
sum2=(sum2+nums2[j]);
j++;
}
}
while(i!=nums1.size()){
sum1=sum1+nums1[i];
i++;
}
while(j!=nums2.size()){
sum2=sum2+nums2[j];
j++;
}
return res=(res+max(sum1,sum2))%mod;
}
};
``````

# leetcode 1536. Minimum Swaps to Arrange a Binary Grid 贪心冒泡排序

#### 题目

https://leetcode.com/contest/weekly-contest-200/problems/minimum-swaps-to-arrange-a-binary-grid/
Given an n x n binary grid, in one step you can choose two adjacent rows of the grid and swap them.

A grid is said to be valid if all the cells above the main diagonal are zeros.

Return the minimum number of steps needed to make the grid valid, or -1 if the grid cannot be valid.

The main diagonal of a grid is the diagonal that starts at cell (1, 1) and ends at cell (n, n).

Example 1:

Input: grid = [[0,0,1],[1,1,0],[1,0,0]]
Output: 3
Example 2:

Input: grid = [[0,1,1,0],[0,1,1,0],[0,1,1,0],[0,1,1,0]]
Output: -1
Explanation: All rows are similar, swaps have no effect on the grid.
Example 3:

Input: grid = [[1,0,0],[1,1,0],[1,1,1]]
Output: 0

Constraints:

n == grid.length
n == grid[i].length
1 <= n <= 200
grid[i][j] is 0 or 1

#### 源码

``````class Solution {
public:
int minSwaps(vector<vector<int>>& grid) {
vector<int> nums;
for(auto p:grid){
int count = 0;
for(int i = p.size()-1;i>=0;--i){
if(p[i]==0){
count++;
}else break;
}
nums.push_back(count);
}
int res = 0;
for(int i = 0;i < nums.size();++i){
if(nums[i] < nums.size()-i-1){
bool f = true;
for(int j = i+1;j < nums.size();++j){
if(nums[j]>=nums.size()-i-1){
int t = nums[j];
nums.erase(nums.begin()+j);
nums.insert(nums.begin()+i,t);
res += j-i;
f = false;
break;
}
}
if(f)return -1;
}
}
return res;
}
};
``````

# leetcode 1547. Minimum Cost to Cut a Stick 区间dp

#### 题目

https://leetcode.com/problems/minimum-cost-to-cut-a-stick/
Given a wooden stick of length n units. The stick is labelled from 0 to n. For example, a stick of length 6 is labelled as follows:

Given an integer array cuts where cuts[i] denotes a position you should perform a cut at.

You should perform the cuts in order, you can change the order of the cuts as you wish.

The cost of one cut is the length of the stick to be cut, the total cost is the sum of costs of all cuts. When you cut a stick, it will be split into two smaller sticks (i.e. the sum of their lengths is the length of the stick before the cut). Please refer to the first example for a better explanation.

Return the minimum total cost of the cuts.

Example 1:

Input: n = 7, cuts = [1,3,4,5]
Output: 16
Explanation: Using cuts order = [1, 3, 4, 5] as in the input leads to the following scenario:

The first cut is done to a rod of length 7 so the cost is 7. The second cut is done to a rod of length 6 (i.e. the second part of the first cut), the third is done to a rod of length 4 and the last cut is to a rod of length 3. The total cost is 7 + 6 + 4 + 3 = 20.
Rearranging the cuts to be [3, 5, 1, 4] for example will lead to a scenario with total cost = 16 (as shown in the example photo 7 + 4 + 3 + 2 = 16).
Example 2:

Input: n = 9, cuts = [5,6,1,4,2]
Output: 22
Explanation: If you try the given cuts ordering the cost will be 25.
There are much ordering with total cost <= 25, for example, the order [4, 6, 5, 2, 1] has total cost = 22 which is the minimum possible.

Constraints:

2 <= n <= 10^6
1 <= cuts.length <= min(n – 1, 100)
1 <= cuts[i] <= n – 1
All the integers in cuts array are distinct.

#### 思路

1000 题合并石堆还简单，是 K = 2 的特殊情况，直接区间 dp AC，参考矩阵乘法结合律优化
cuts 数组直接作为向前累加和，注意排序

#### 源码

``````class Solution {
public:;
;
int minCost(int n, vector<int>& cuts) {
cuts.push_back(n);
sort(begin(cuts),end(cuts));
vector<vector<int>> dp(cuts.size()+1,vector<int>(cuts.size()+1,INT_MAX));
return calDp(0,cuts.size()-1,cuts,dp);
}
int calDp(int i,int j,vector<int>& cuts,vector<vector<int>>&dp){
if(dp[i][j] != INT_MAX){
return dp[i][j];
}
if(i == j){
return dp[i][j] = 0;
}else if(i+1 == j){
return dp[i][j] = cuts[j]-(i==0?0:cuts[i-1]);
}else{
for(int k = i;k < j;++k){
dp[i][j]=min(dp[i][j],calDp(i,k,cuts,dp)+calDp(k+1,j,cuts,dp)+cuts[j]-(i==0?0:cuts[i-1]));
}
}
return dp[i][j];
}
};
``````

# leetcode 1000. Minimum Cost to Merge Stones 区间dp 归并

#### 题目

https://leetcode.com/problems/minimum-cost-to-merge-stones/
There are N piles of stones arranged in a row. The i-th pile has stones[i] stones.

A move consists of merging exactly K consecutive piles into one pile, and the cost of this move is equal to the total number of stones in these K piles.

Find the minimum cost to merge all piles of stones into one pile. If it is impossible, return -1.

Example 1:

Input: stones = [3,2,4,1], K = 2
Output: 20
Explanation:
We merge [3, 2] for a cost of 5, and we are left with [5, 4, 1].
We merge [4, 1] for a cost of 5, and we are left with [5, 5].
We merge [5, 5] for a cost of 10, and we are left with [10].
The total cost was 20, and this is the minimum possible.
Example 2:

Input: stones = [3,2,4,1], K = 3
Output: -1
Explanation: After any merge operation, there are 2 piles left, and we can’t merge anymore. So the task is impossible.
Example 3:

Input: stones = [3,5,1,2,6], K = 3
Output: 25
Explanation:
We merge [5, 1, 2] for a cost of 8, and we are left with [3, 8, 6].
We merge [3, 8, 6] for a cost of 17, and we are left with [17].
The total cost was 25, and this is the minimum possible.

Note:

1 <= stones.length <= 30
2 <= K <= 30
1 <= stones[i] <= 100

#### 源码

``````class Solution {
public:
vector<vector<vector<long>>> dp;
vector<int> pre;
int DK;
int mergeStones(vector<int>& stones, int K) {
DK = K;
dp.resize(stones.size()+1,vector<vector<long>>(stones.size()+1,vector<long>(K+1,INT_MAX)));
pre.resize(stones.size()+1,0);
for(int i = 0;i < stones.size();++i){
pre[i]=pre[i==0?0:i-1]+stones[i];
}
return calDp(0,stones.size()-1,1)==INT_MAX?-1:calDp(0,stones.size()-1,1);
}
long calDp(int st,int ed,int k){
if(dp[st][ed][k]!=INT_MAX)return dp[st][ed][k];
if(st==ed){
return dp[st][ed][k] = k==1?0:INT_MAX;
}
if((ed-st-k+1)%(DK-1)!=0){
return dp[st][ed][k] = INT_MAX;
}
if(k == 1){
return dp[st][ed][1] = calDp(st,ed,DK)+pre[ed]-(st==0?0:pre[st-1]);
}
for(int t = st;t < ed;t += (DK-1)){
dp[st][ed][k] = min(dp[st][ed][k],calDp(st,t,1)+calDp(t+1,ed,k-1));
}
return dp[st][ed][k];
}
};
``````

# leetcode 1546. Maximum Number of Non-Overlapping Subarrays With Sum Equals Target 动态规划 向前累积和

#### 题目

https://leetcode.com/contest/weekly-contest-201/problems/maximum-number-of-non-overlapping-subarrays-with-sum-equals-target/
Given an array nums and an integer target.

Return the maximum number of non-empty non-overlapping subarrays such that the sum of values in each subarray is equal to target.

Example 1:

Input: nums = [1,1,1,1,1], target = 2
Output: 2
Explanation: There are 2 non-overlapping subarrays [1,1,1,1,1] with sum equals to target(2).
Example 2:

Input: nums = [-1,3,5,1,4,2,-9], target = 6
Output: 2
Explanation: There are 3 subarrays with sum equal to 6.
([5,1], [4,2], [3,5,1,4,2,-9]) but only the first 2 are non-overlapping.
Example 3:

Input: nums = [-2,6,6,3,5,4,1,2,8], target = 10
Output: 3
Example 4:

Input: nums = [0,0,0], target = 0
Output: 3

Constraints:

1 <= nums.length <= 10^5
-10^4 <= nums[i] <= 10^4
0 <= target <= 10^6

#### 源码

``````class Solution {
public:
vector<int> dp,s;
map<int,int> m;
int maxNonOverlapping(vector<int>& nums, int target) {
dp.resize(nums.size()+1,0);
s.resize(nums.size()+1,0);
int sum = 0;

for(int i = 0;i<nums.size();++i){
sum+=nums[i];
s[i]=sum;

dp[i] = dp[i==0?0:i-1];
if(nums[i]==target){
dp[i]++;
cout<<"a "<<i<<" "<<dp[i]<<endl;
m[sum] = i;
continue;
}
if(m.count(s[i]-target)!=0){
dp[i]=max(dp[i],dp[m[s[i]-target]]+1);
cout<<"b "<<i<<" "<<dp[i]<<endl;
}else if(s[i]==target){
dp[i]=max(dp[i],1);
cout<<"c "<<i<<" "<<dp[i]<<endl;
}
m[sum] = i;

}
return dp[nums.size()-1];
}
};
``````

# leetcode 698. Partition to K Equal Sum Subsets 分支限界

#### 题目

https://leetcode.com/problems/partition-to-k-equal-sum-subsets/
Given an array of integers nums and a positive integer k, find whether it’s possible to divide this array into k non-empty subsets whose sums are all equal.

Example 1:

Input: nums = [4, 3, 2, 3, 5, 2, 1], k = 4
Output: True
Explanation: It’s possible to divide it into 4 subsets (5), (1, 4), (2,3), (2,3) with equal sums.

Note:

1 <= k <= len(nums) <= 16.
0 < nums[i] < 10000.

#### 思路

dfs 分支限界直接回溯，dfs实际上是考虑到了所有的组合的，所以不用担心排列组合导致的无法划分为k个子集的情况，代码中的 flag 标志计算使用 dfs 递归遍历所有组合

#### 源码

``````class Solution {
public:
int avg;
bool canPartitionKSubsets(vector<int>& nums, int k) {
int sum = 0;
for(auto p:nums){
sum+=p;
}
if(sum % k !=0) return false;
avg =  sum / k;
vector<bool> vis(nums.size(),false);
return dfs(nums.size()-1,avg,nums,nums.size(),vis);
}
bool dfs(int start,int target,vector<int> &nums,int remains,vector<bool> &vis){
if(remains==0)return true;
bool flag = false;
for(int i = start;i >= 0;--i){
if(!vis[i]&&target>=nums[i]){
vis[i]=true;
if(target == nums[i])flag = dfs(nums.size()-1,avg,nums,remains-1,vis);
else flag = dfs(i-1,target-nums[i],nums,remains-1,vis);
if(flag)return flag;
vis[i]=false;
// while(i>=1&&nums[i]==nums[i-1])i--;
}
}
return flag;
}
};
``````

# leetcode 474 Ones and Zeroes 双维度01背包问题

#### 题目

https://leetcode.com/problems/ones-and-zeroes/submissions/

#### 源码

``````class Solution {
public:
vector<int> ones;
vector<int> zeros;
vector<vector<int>> mn;
int findMaxForm(vector<string>& strs, int m, int n) {
if(strs.size()==0)return 0;
if(m==0&&n==0)return 0;
ones.resize(strs.size());
zeros.resize(strs.size());
mn.resize(m+1,vector<int>(n+1,0));
for(int i = 0;i < strs.size();++i){
int o = 0;
for(int k = 0;k < strs[i].size();++k){
if(strs[i][k]=='1')o++;
}
ones[i]=o;
zeros[i]=strs[i].length()-o;
}
//bag
for(int i = 0;i < strs.size();++i){
//cout<<endl <<i<<endl;
for(int m1 = m;m1>=zeros[i];--m1){
for(int n1 = n;n1>=ones[i];--n1){
mn[m1][n1]=max(mn[m1][n1],mn[m1-zeros[i]][n1-ones[i]]+1);
//cout <<m1<<","<<n1<<" = "<<mn[m1][n1]<<endl;
}
}
}
return mn[m][n];
}
};
``````

# leetcode 322 Coin Change 完全背包

#### 题目

https://leetcode.com/problems/coin-change/submissions/

#### 思路

https://zhuanlan.zhihu.com/p/141627678?from_voters_page=true
min 类型的完全背包问题，和零一背包的唯一区别在于 j 从 coins 开始，这样可以复用之间 的结果，该写法是状态压缩的写法

#### 源码

``````class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
vector<int>dp(amount+1,INT_MAX-10);
dp[0] = 0;
for(int i = 0;i < coins.size();++i){
for(int j = coins[i];j <=amount;++j){
if(dp[j] != INT_MAX)
dp[j] = min(dp[j],dp[j-coins[i]]+1);
}
}
return dp[amount]==INT_MAX-10?-1:dp[amount];
}
};
``````