1.最后一块石头的重量II（1049题）
题目描述：
有一堆石头，每块石头的重量都是正整数。
每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：
如果 x == y，那么两块石头都会被完全粉碎；
如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。
最后，最多只会剩下一块石头。返回此石头最小的可能重量。如果没有石头剩下，就返回 0。
示例：
- 输入：[2,7,4,1,8,1]
- 输出：1
解释：
- 组合 2 和 4，得到 2，所以数组转化为 [2,7,1,8,1]，
- 组合 7 和 8，得到 1，所以数组转化为 [2,1,1,1]，
- 组合 2 和 1，得到 1，所以数组转化为 [1,1,1]，
- 组合 1 和 1，得到 0，所以数组转化为 [1]，这就是最优值
dp[j]表示容量（这里说容量更形象，其实就是重量）为j的背包，最多可以背最大重量为dp[j]。
01背包的递推公式为：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
本题则是：dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);
提示中给出1 <= stones.length <= 30，1 <= stones[i] <= 1000，所以最大重量就是30 * 1000 。
而我们要求的target其实只是最大重量的一半，所以dp数组开到15000大小就可以了。
当然也可以把石头遍历一遍，计算出石头总重量 然后除2，得到dp数组的大小。
我这里就直接用15000了。
接下来就是如何初始化dp[j]呢，因为重量都不会是负数，所以dp[j]都初始化为0就可以了，这样在递归公式dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);中dp[j]才不会初始值所覆盖。
如果使用一维dp数组，物品遍历的for循环放在外层，遍历背包的for循环放在内层，且内层for循环倒序遍历！
那么分成两堆石头，一堆石头的总重量是dp[target]，另一堆就是sum - dp[target]。
在计算target的时候，target = sum / 2 因为是向下取整，所以sum - dp[target] 一定是大于等于dp[target]的。
那么相撞之后剩下的最小石头重量就是 (sum - dp[target]) - dp[target]。
class Solution {
public:
int lastStoneWeightII(vector<int>& stones) {
int sum = 0;//计算总和
vector<int>dp(15001,0);//定义初始化dp数组
//求石头总和
for(int i = 0;i < stones.size();i++){
sum += stones[i];
}
//目标和为其一半
int target = sum / 2;
//遍历顺序，遍历物品，
for(int i = 0;i < stones.size();i++){
//遍历背包，从后向前遍历
for(int j = target;j >= stones[i];j--){
dp[j] = max(dp[j],dp[j-stones[i]]+stones[i]);//递推公式，实现
}
}
return sum - dp[target] - dp[target];//目标最靠近的值，两个差就是所求
}
};- 时间复杂度：O(m × n) , m是石头总重量（准确的说是总重量的一半），n为石头块数
- 空间复杂度：O(m)
2. 目标和（494题）
题目描述：
给定一个非负整数数组，a1, a2, ..., an, 和一个目标数，S。现在你有两个符号 + 和 -。对于数组中的任意一个整数，你都可以从 + 或 -中选择一个符号添加在前面。
返回可以使最终数组和为目标数 S 的所有添加符号的方法数。
示例：
- 输入：nums: [1, 1, 1, 1, 1], S: 3
- 输出：5
解释：
- -1+1+1+1+1 = 3
- +1-1+1+1+1 = 3
- +1+1-1+1+1 = 3
- +1+1+1-1+1 = 3
- +1+1+1+1-1 = 3
一共有5种方法让最终目标和为3。
既然为target，那么就一定有 left组合 - right组合 = target。
left + right = sum，而sum是固定的。right = sum - left
公式来了， left - (sum - left) = target 推导出 left = (target + sum)/2 。
target是固定的，sum是固定的，left就可以求出来
回溯算法：
class Solution {
private:
vector<vector<int>>result;//结果集
vector<int>path;//路径
//定义回溯函数，转变为组合问题，startindex，
void backtracking(vector<int>& candicate,int target,int sum,int startindex){
//终止条件
if(sum == target){
result.push_back(path);
}
//遍历，从startindex开始
for(int i = startindex;i < candicate.size() && sum + candicate[i] <= target;i++){
sum += candicate[i];//递归
path.push_back(candicate[i]);//加入路径
backtracking(candicate,target,sum,i+1);//递归函数
sum -= candicate[i];//回溯
path.pop_back();//回溯
}
}
public:
int findTargetSumWays(vector<int>& nums, int target) {
int sum = 0;//总和
for(int i = 0;i < nums.size();i++)sum += nums[i];//计算总和
if(target > sum)return 0;//如果目标值大于总和，返回0
if((target+sum)%2)return 0;//如果相除除不开，返回0
int bagSize = (target + sum) / 2;
result.clear();
path.clear();
sort(nums.begin(), nums.end());//需要排序
backtracking(nums, bagSize, 0, 0);
return result.size();
}
};动态规划：
转化为01背包问题
假设加法的总和为x，那么减法对应的总和就是sum - x。
所以我们要求的是 x - (sum - x) = target
x = (target + sum) / 2
此时问题就转化为，装满容量为x的背包，有几种方法。
dp[j] 表示：填满j（包括j）这么大容积的包，有dp[j]种方法
只要搞到nums[i]，凑成dp[j]就有dp[j - nums[i]] 种方法。
dp[j] += dp[j - nums[i]]背包解决排列组合问题
dp[0] 一定要初始化为1
01背包问题一维dp的遍历，nums放在外循环，target在内循环，且内循环倒序。
class Solution {
public:
int findTargetSumWays(vector<int>& nums, int target) {
int sum = 0;//总和
for(int i = 0;i < nums.size();i++)sum += nums[i];//求总和
if (abs(target) > sum) return 0; // 此时没有方案
if ((target + sum) % 2 == 1) return 0; // 此时没有方案
int bagsize = (target+sum)/2;//求包大小
vector<int>dp(bagsize+1,0);//定义dp数组，且初始化
dp[0] = 1;//给dp[0]定义为1
//遍历外层遍历nums
for(int i = 0;i < nums.size();i++){
//内层循环是bag，，
for(int j = bagsize;j >= nums[i];j--){
dp[j] += dp[j-nums[i]];//递推公式，主要求有多少种方法，组合问题
}
}
return dp[bagsize];//返回
}
};- 时间复杂度：O(n × m)，n为正数个数，m为背包容量
- 空间复杂度：O(m)，m为背包容量
3.一和零（474题）
题目描述：
给你一个二进制字符串数组 strs 和两个整数 m 和 n 。
请你找出并返回 strs 的最大子集的大小，该子集中 最多 有 m 个 0 和 n 个 1 。
如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 。
示例 1：
-
输入：strs = ["10", "0001", "111001", "1", "0"], m = 5, n = 3
-
输出：4
-
解释：最多有 5 个 0 和 3 个 1 的最大子集是 {"10","0001","1","0"} ，因此答案是 4 。 其他满足题意但较小的子集包括 {"0001","1"} 和 {"10","1","0"} 。{"111001"} 不满足题意，因为它含 4 个 1 ，大于 n 的值 3 。
dp[i][j]：最多有i个0和j个1的strs的最大子集的大小为dp[i][j]。
dp[i][j] 可以由前一个strs里的字符串推导出来，strs里的字符串有zeroNum个0，oneNum个1。
dp[i][j] 就可以是 dp[i - zeroNum][j - oneNum] + 1。
然后我们在遍历的过程中，取dp[i][j]的最大值。
所以递推公式：dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);
因为物品价值不会是负数，初始为0，保证递推的时候dp[i][j]不会被初始值覆盖。
物品就是strs里的字符串，背包容量就是题目描述中的m和n
class Solution {
public:
int findMaxForm(vector<string>& strs, int m, int n) {
vector<vector<int>>dp(m+1,vector<int>(n+1,0));//定义dp数组，并且初始化为0
//遍历字符串的每一个字符串
for(string str : strs){
//记录0和1的个数
int onenum = 0,zeronum = 0;
//记录每一个字符串的01个数
for(char c : str){
if(c == '0')zeronum++;
else onenum++;
}
遍历背包容量且从后向前遍历
for(int i = m;i >= zeronum;i--){
for(int j = n;j >= onenum;j--){
dp[i][j] = max(dp[i][j],dp[i-zeronum][j-onenum] + 1);//递推公式，根据01背包来写的
}
}
}
return dp[m][n];
}
};- 时间复杂度: O(kmn)，k 为strs的长度
- 空间复杂度: O(mn)
4.动态规划：完全背包理论基础 (卡码网第52题）
完全背包
有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品都有无限个（也就是可以放入背包多次），求解将哪些物品装入背包里物品价值总和最大。
完全背包和01背包问题唯一不同的地方就是，每种物品有无限件。
01背包和完全背包唯一不同就是体现在遍历顺序上
01背包的核心代码：
for(int i = 0; i < weight.size(); i++) { // 遍历物品
for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
}
}01背包内嵌的循环是从大到小遍历，为了保证每个物品仅被添加一次。
而完全背包的物品是可以添加多次的，所以要从小到大去遍历
// 先遍历物品，再遍历背包
for(int i = 0; i < weight.size(); i++) { // 遍历物品
for(int j = weight[i]; j <= bagWeight ; j++) { // 遍历背包容量
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
}
}在完全背包中，对于一维dp数组来说，其实两个for循环嵌套顺序是无所谓的
#include <iostream>
#include <vector>
using namespace std;
// 先遍历背包，再遍历物品
void test_CompletePack(vector<int> weight, vector<int> value, int bagWeight) {
vector<int> dp(bagWeight + 1, 0);
for(int j = 0; j <= bagWeight; j++) { // 遍历背包容量
for(int i = 0; i < weight.size(); i++) { // 遍历物品
if (j - weight[i] >= 0) dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
}
}
cout << dp[bagWeight] << endl;
}
int main() {
int N, V;
cin >> N >> V;
vector<int> weight;
vector<int> value;
for (int i = 0; i < N; i++) {
int w;
int v;
cin >> w >> v;
weight.push_back(w);
value.push_back(v);
}
test_CompletePack(weight, value, V);
return 0;
}5.零钱兑换II（518题）
题目描述：
给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。
示例 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
纯完全背包是凑成背包最大价值是多少，而本题是要求凑成总金额的物品组合个数！组合不强调元素之间的顺序，排列强调元素之间的顺序。
dp[j]：凑成总金额j的货币组合数为dp[j]
dp[j] 就是所有的dp[j - coins[i]]（考虑coins[i]的情况）相加。
所以递推公式：dp[j] += dp[j - coins[i]];
首先dp[0]一定要为1，dp[0] = 1是 递归公式的基础
外层for循环遍历物品（钱币），内层for遍历背包（金钱总额）
for (int i = 0; i < coins.size(); i++) { // 遍历物品
for (int j = coins[i]; j <= amount; j++) { // 遍历背包容量
dp[j] += dp[j - coins[i]];
}
}这种遍历顺序中dp[j]里计算的是组合数
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]];
}
}dp[j]里算出来的就是排列数
class Solution {
public:
int change(int amount, vector<int>& coins) {
vector<int>dp(amount + 1,0);//设定dp数组含义，和对其其他非0元素初始化为0
dp[0] = 1;//对0元素初始化为1
//遍历顺序为外层物品，内层为背包，这个是需要组合数，相反则是排列数
for(int i = 0; i < coins.size();i++){
//注意遍历时，起始位置和终止位置边界
for(int j = coins[i];j <= amount;j++){
dp[j] += dp[j - coins[i]];//递推公式是01背包的推导
}
}
return dp[amount];
}
};- 时间复杂度: O(mn)，其中 m 是amount，n 是 coins 的长度
- 空间复杂度: O(m)
6.组合总和 Ⅳ（377题）
题目描述：
给定一个由正整数组成且不存在重复数字的数组，找出和为给定目标正整数的组合的个数。
示例:
- nums = [1, 2, 3]
- target = 4
所有可能的组合为： (1, 1, 1, 1) (1, 1, 2) (1, 2, 1) (1, 3) (2, 1, 1) (2, 2) (3, 1)
请注意，顺序不同的序列被视作不同的组合。
因此输出为 7。
本质是本题求的是排列总和，而且仅仅是求排列总和的个数，并不是把所有的排列都列出来。
如果本题要把排列都列出来的话，只能使用回溯算法爆搜。
dp[i]: 凑成目标正整数为i的排列个数为dp[i]
求装满背包有几种方法，递推公式一般都是dp[i] += dp[i - nums[j]];
因为递推公式dp[i] += dp[i - nums[j]]的缘故，dp[0]要初始化为1，这样递归其他dp[i]的时候才会有数值基础。
个数可以不限使用，说明这是一个完全背包。
得到的集合是排列，说明需要考虑元素之间的顺序。
本题要求的是排列，那么这个for循环嵌套的顺序可以有说法了。
如果求组合数就是外层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 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];
}
};- 时间复杂度: O(target * n)，其中 n 为 nums 的长度
- 空间复杂度: O(target)
7.爬楼梯（进阶版）(卡玛网57题）
题目描述：
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬至多m (1 <= m < n)个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。
输入描述：输入共一行，包含两个正整数，分别表示n, m
输出描述：输出一个整数，表示爬到楼顶的方法数。
输入示例：3 2
输出示例：3
提示：
当 m = 2，n = 3 时，n = 3 这表示一共有三个台阶，m = 2 代表你每次可以爬一个台阶或者两个台阶。
此时你有三种方法可以爬到楼顶。
- 1 阶 + 1 阶 + 1 阶段
- 1 阶 + 2 阶
- 2 阶 + 1 阶
dp[i]：爬到有i个台阶的楼顶，有dp[i]种方法。
递推公式为：dp[i] += dp[i - j]
递归公式是 dp[i] += dp[i - j]，那么dp[0] 一定为1，dp[0]是递归中一切数值的基础所在，如果dp[0]是0的话，其他数值都是0了。
将target放在外循环，将nums放在内循环。
每一步可以走多次，这是完全背包，内循环需要从前向后遍历
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n, m;
while (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] << endl;
}
}- 时间复杂度: O(n * m)
- 空间复杂度: O(n)
总结：
最后一块石头的重量II：dp[j]表示容量（这里说容量更形象，其实就是重量）为j的背包，最多可以背最大重量为dp[j]，选出任意两块石头，然后将它们一起粉碎，就是01背包问题，递推公式dp[j] = max(dp[j], dp[j - stones[i]] + stones[i])，使用一维dp数组，物品遍历的for循环放在外层，遍历背包的for循环放在内层，且内层for循环倒序遍历，dp[j]都初始化为0，一堆石头的总重量是dp[target]，另一堆就是sum - dp[target]，最小石头重量就是(sum - dp[target]) - dp[target]，
目标和：给定一组数，通过加减的方式达到目标和的方法，最后求达到这个方法的总数，target，那么就一定有 left组合 - right组合 = target，left + right = sum，而sum是固定的。right = sum - left，left - (sum - left) = target 推导出 left = (target + sum)/2，target是固定的，sum是固定的，left就可以求出来，回溯法可以解决，回溯法收集每个路径，所以需要两个数组，一个是路径，一个是结果集，组合问题，不要忘记startindex，定义终止条件，其实就是sum == target，如果得到了就将路径加入结果集，从startindex开始遍历，求sum值，然后加入路径，在之后我们需要进行递归，再进行弹出，减值回溯，这里我们需要进行排序，动态规划方法来实现，问题就转化为，装满容量为x的背包，有几种方法，dp[j] 表示：填满j（包括j）这么大容积的包，有dp[j]种方法，就是混和组合问题，求组合的递推公式是dp[j] += dp[j - nums[i]]，dp[0] 一定要初始化为1，01背包问题一维dp的遍历，nums放在外循环，target在内循环，且内循环倒序。这里先求出sum，已知target所以可以求出背包容量，这里注意遍历顺序
一和零：一个二进制字符串，里面给定两个参数m,n，不超过这两个01的最多子集数，dp[i][j]：最多有i个0和j个1的strs的最大子集的大小为dp[i][j]，dp[i][j] 就可以是 dp[i - zeroNum][j - oneNum] + 1，dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1)，初始为0，物品就是strs里的字符串，背包容量就是题目描述中的m和n，我们这里注意定义二维数组的大小要M+1,n+1的二维数组，我们首先需要知道每个字符串的0和1的个数，这里注意再遍历背包和物品时候，边界m-onenum,n-zeronum,且倒序遍历，最后返回dp[m][n]即可
完全背包理论基础：有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品都有无限个（也就是可以放入背包多次），求解将哪些物品装入背包里物品价值总和最大。与01背包不同之处在于物品可以多次取用，这里需要掌握01背包核心代码，for(int i = 0; i < weight.size(); i++) { // 遍历物品，一维数组来实现，外层物品，内层背包，
for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量 倒序
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
}
}01背包从大到小遍历是因为保证只添加一次物品，
for(int i = 0; i < weight.size(); i++) { // 遍历物品
for(int j = weight[i]; j <= bagWeight ; j++) { // 遍历背包容量，这里顺序和01背包一样，只不过遍历顺序变了，注意边界
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
}
}完全背包中，对于一维dp数组来说，其实两个for循环嵌套顺序是无所谓的
零钱兑换II:给定一堆零钱，和一个总额，要求凑成总额的方法数量， 要求凑成总金额的物品组合个数，dp[j]：凑成总金额j的货币组合数为dp[j]，递推公式：dp[j] += dp[j - coins[i]];dp[0]一定要为1，外层for循环遍历物品（钱币），内层for遍历背包（金钱总额）
for (int i = 0; i < coins.size(); i++) { // 遍历物品
for (int j = coins[i]; j <= amount; j++) { // 遍历背包容量
dp[j] += dp[j - coins[i]];
}
}
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]];
}
}这两种写法一样的概念
组合总和IV:给定一个数组，然后通过目标值，通过对组合来求出，顺序不同也可以作为不同的序列，求序列个数，所以这个是标准的排列问题，求排列个数，如果求排列组合的写法需要回溯法来实现，dp[i]: 凑成目标正整数为i的排列个数为dp[i] ，递推公式一般都是dp[i] += dp[i - nums[j]]，dp[0]要初始化为1，如果求组合数就是外层for循环遍历物品，内层for遍历背包。如果求排列数就是外层for遍历背包，内层for循环遍历物品。这里注意一下如果是排列的，需要加入判断条件，保证递推公式有意义
爬楼梯进阶版：正在爬楼梯。需要 n 阶你才能到达楼顶，每次可以爬至多m (1 <= m < n)个台阶。有多少种不同的方法可以爬到楼顶，dp[i]：爬到有i个台阶的楼顶，有dp[i]种方法，递推公式为：dp[i] += dp[i - j]，dp[0] 一定为1，先遍历背包再遍历物品注意条件设定和边界取值，注意不要让dp无意义，
标签：遍历,target,int,sum,学习心得,C++,算法,背包,dp From： https://blog.csdn.net/weixin_55605689/article/details/136124857