简单记录刷题的过程（大佬勿喷）

一和零

https://leetcode-cn.com/problems/ones-and-zeroes/
多维0-1背包问题： 把题目给定的 0 的数量看成一个背包， 1的数量看成另一个背包，把数组中的每一个字符串看成一件件商品，统计每一个字符串 0 和 1的数量，动态规划填表
状态转移方程：dp[i][j] = max(dp[i][j],1+dp[i-count0][j-count1])，其中 dp[i][j]为使用 i个 0 和 j 个 1能表示字符串的最大数量，count0 为数组中每个字符串中 0 的数量， count1为数组中每个字符串 1 的数量

class Solution {
public:int findMaxForm(vector<string>& strs, int m, int n) {int N = strs.size();if(N==0){return 0;}int dp[m+1][n+1];memset(dp,0,sizeof(int)*(m+1)*(n+1));for(int i = 0; i<N; i++){int count1 = 0;int count2 = 0;for(int j = 0; j<strs[i].size(); j++){if(strs[i][j]=='0')count1++;//0 的数量else{count2++;// 1 的数量}}//01背包，每个数据只能取一次//倒序循环，避免数据被重复选择for(int k = m; k>=count1;k--){for(int r = n; r>=count2; r--){dp[k][r] = max(dp[k-count1][r-count2]+1, dp[k][r]);}}}return dp[m][n];}
};

分割等和子集

https://leetcode-cn.com/problems/partition-equal-subset-sum/
思路：题意是判断是否能将一个数组分割成元素和相同的子集，那么自然可以想到数组的元素总和必须是偶数，否则无法一分为二。题目转化为从数组中找出一些元素让它们的和等于数组总和的一半（固定的值），因此可以想到利用 0-1背包的思想解题，把固定和看成背包的容量（直接套模板）

class Solution {
public:bool canPartition(vector<int>& nums) {int n = nums.size();int sum = 0;for(int i = 0; i<n;i++){sum += nums[i];}if(sum%2==1){return false;}int temp = sum/2;int dp[temp+1];memset(dp,0,sizeof(int)*(temp+1));dp[0] = true;for(int i = 0; i<n; i++){for(int j = temp; j>=nums[i];j--){dp[j] = dp[j]||dp[j-nums[i]];}}return dp[temp];}
};

目标和

https://leetcode-cn.com/problems/target-sum/
因此，题目求元素和等价于求数组中元素和等于（nums数组元素总和+S）/ 2 的方案数有多少。

class Solution {
public:int findTargetSumWays(vector<int>& nums, int S) {int sum = 0;for(int i = 0; i<nums.size(); i++){sum += nums[i];}if(sum<S||(S+sum)%2==1){return 0;}int val = (S+sum)/2;int dp[val+1];memset(dp,0,sizeof(int)*(val+1));//注意初始化dp[0] = 1;//初始状态：总和等于 0 的方案数（因为可以一个都不取，因此方案数等于1）for(int i = 0; i<nums.size();i++){for(int j = val; j>=nums[i];j--){dp[j] = dp[j]+ dp[j-nums[i]];//因为是求方案数，所以是加和}}return dp[val];}
};

零钱兑换

https://leetcode-cn.com/problems/coin-change/
这道题可以看成是完全背包问题，注意一些小的区别（1）原始完全背包问题要求不超过，但是本题是恰好等于amount（2）题目求的是总价值最少，但是完全背包问题是求总价值最大
思路：以coins = [1,2,5]，amount = 11为例，f(i)表示凑成金额为 i 所需要的最少硬币数

因此，f[j] = min(1 + f[j - coins[i]]，f[j]) i = [0, coins.size() - 1] （注意：前提是硬币的面值要小于当前的金额，否则无法使用，且剩余的面值也要能够凑出来），根据状态方程就可以（直接套用完全背包的模板）解题，因为要求最小值，所以dp初始化时要用尽量大的值

class Solution {
public:int coinChange(vector<int>& coins, int amount) {if(coins.size()==0){return -1;}int dp[amount+1];//注意不能用memset(dp,INT_MAX,sizeof(int)*(amount+1))否则会溢出，得不到想要的结果for(int k = 0; k<amount+1; k++){dp[k] = 99999;//初始化}dp[0] = 0;for(int i = 0; i<coins.size();i++){for(int j = coins[i]; j<=amount; j++){//dp[j-coins[i]]必须有值，如果dp[j-coins[i]]是无穷大//说明无法凑出j-coins[i]价值的钱包，那么把coins[i]放进去以后，自然也凑不出dp[j]的钱包if(dp[j-coins[i]]!=99999)dp[j] = min(dp[j],dp[j-coins[i]]+1);//放入和不放入的情况}}return dp[amount]==99999?-1:dp[amount];}
};

零钱兑换 II

https://leetcode-cn.com/problems/coin-change-2/
(是“零钱兑换”一题的变种，求的是方案数）所以 状态方程改为求和而不是最小值，注意数组初始化为0，初始状态：amount等于 0 的方案数（因为可以一个都不取，因此方案数等于1）（跟上面“目标和”一题求0-1背包的方案数也很相似）

class Solution {
public:int change(int amount, vector<int>& coins) {int dp[amount+1];memset(dp,0,sizeof(int)*(amount+1));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];}
};

单词拆分

https://leetcode-cn.com/problems/word-break/
思路：用dp[i] 表示子串 s[0…i] ，假设这段子串可以被拆分，并且拆分以后的单词落在 给定的字典 中，而且子串后面的单词s[i+1…s.size()]也落在给定的字典中，即可判断 dp[i]为真。因此通过不断更新 dp 数组来实现上述过程，最终dp[len]的值为真or 假即为所求最终结果。
注意初始状态 dp[0]为true，因为如果给定的字符串本身就在给定的字典里面了，就可以直接判断为真，而不必再进行 j 的递增寻找 dp 的状态了。
一些知识点：
1.C++的substr函数的用法：
例如：string s(“12345abcd”);
string a = s.substr(0,5); //获得字符串s中从第0位开始的长度为5的字符串
输出的结果是 “12345”

2.C++中vector使用find函数：不同于map、set、multiset、multimap，vector本身是没有find这个方法，即不能使用 .find()调用，而是依靠头文件algorithm来实现find函数。
形式是：find（a.begin(),a.end(),value）

解题的思路：

效率还不是很高www，欢迎大家指教

class Solution {
public:bool wordBreak(string s, vector<string>& wordDict) {if(s.empty()||wordDict.empty()){return false;}int len = s.size();vector<bool> dp(len+1, false);dp[0] = true;for(int i = 1; i<=len; i++){for(int j = 0; j<i;j++){if(dp[j]&& find(wordDict.begin(),wordDict.end(),s.substr(j,i-j))!=wordDict.end()){dp[i] = true;break;} }}return dp[len];}
};

组合总和 Ⅳ

https://leetcode-cn.com/problems/combination-sum-iv/
这道题跟前面的零钱兑换 II很相似，两者的区别是本题是顺序不同的序列被视作不同的组合，即{1,2}，{2,1}视为两种组合方式。因此，对于有顺序的背包问题时，方法可以改为以target为外循环，以数组元素的作为内循环，状态转移方程为dp[i] = dp[i-nums[0]] + dp[i-nums[1] + dp[i-nums[2]]+……dp[i-nums[len-1]]，len 为nums 数组的长度
（如果想知道有顺序和没顺序的背包问题两者之间的区别，不妨演算一遍，代码下面附上我的演算过程）

class Solution {
public:int combinationSum4(vector<int>& nums, int target) {/* 如果写成这样初始化会报错，因为使用变量来定义数组长度时，数组可以定义但不能同时进行初始化赋值，需要在之后赋值。unsigned long long dp[target+1]={0};*/unsigned long long dp[target+1];memset(dp,0,sizeof(unsigned long long)*(target+1));dp[0] = 1;for(int i = 1; i<=target; i++){for(int j = 0; j<nums.size();j++){if(i-nums[j]>=0 && dp[i-nums[j]]!=0)dp[i] = dp[i]+dp[i-nums[j]];}}return dp[target];}
};

以本题为例对比有顺序和无顺序方案数for循环内外颠倒的产生的不同结果

最后还想分享两个学习动态规划的资料：
经典的背包九讲：https://github.com/tianyicui/pack
动态规划的b站视频：https://www.bilibili.com/video/BV1a4411y7uh?p=1