算法知识点————背包问题【动态规划】【打家劫舍】

万能头文件#include<bits/stdc++.h>

01 背包

定义：物品只能用1次。01对应选还是不选第i个物品 .N个物品、V容量的最大价值。
思路：
（1）f[ i ] [j] 表示前i个物品容量j的最大价值。

（2）当前背包容量不够（j < V[i]），不能选i了，此时最大价值是前i-1和物品的最大价值。f[i] [j] = f[i-1] [j]

(3) 容量够用。可以选i也可以不选i。

选i。f[i] [j] = f[i-1] [j-V[i]] + w[i]

不选i。f[i] [j] = f[i-1] [j]

这两种情况取最值max()

#include<bits/stdc++.h>
using namespace std;
const int MAXX = 1010;
int f[MAXX][MAXX];//f[i][j] 前i个物品容量j的最大价值
int v[MAXX]; // 体积
int w[MAXX]; // 价值
int main(){int n,m;cin>>n>>m;for(int i=1;i<=n;i++) cin>>v[i]>>w[i];for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(j < v[i]){//此时不能装下第i个物品，最优解是前i-1的最优解f[i][j] = f[i-1][j];}else{f[i][j] = max(f[i-1][j],f[i-1][j-v[i]] + w[i]);//此时能装下第i个物品但是选不选i这个物品这两种情况的价值要取最大的}}}cout<<f[n][m]<<endl;return 0;
}

优化：成一维

（1） f[j] 容量j下的最优解

（2）这里的j应该逆序更新

（3） f[j] = max(f[j] , f[j-v[i] ] + w[i] )

#include<bits/stdc++.h>
using namespace std;
const int MAXX = 1010;
int f[MAXX];//f[j] 容量j的最大价值
int v[MAXX]; // 体积
int w[MAXX]; // 价值
int main(){int n,m;cin>>n>>m;for(int i=1;i<=n;i++) cin>>v[i]>>w[i];for(int i=1;i<=n;i++){//for(int j=m;j>=0;j--){for(int j=m;j>= v[i];j--){//if(j < v[i]){//此时不能装下第i个物品，最优解是前i-1的最优解// f[j] = f[j];// }else{f[j] = max(f[j],f[j-v[i]] + w[i]);//此时能装下第i个物品但是选不选i这个物品这两种情况的价值要取最大的// }}}cout<<f[m]<<endl;return 0;
}

优化输入

#include<bits/stdc++.h>
using namespace std;
const int MAXX = 1010;
int f[MAXX];//f[j] 容量j的最大价值
int main(){int n,m;cin>>n>>m;// for(int i=1;i<=n;i++) cin>>v[i]>>w[i];for(int i=1;i<=n;i++){int v,w;cin>>v>>w;//一边输入一边处理for(int j=m;j>= v;j--){f[j] = max(f[j],f[j-v] + w);//此时能装下第i个物品但是选不选i这个物品这两种情况的价值要取最大的}}cout<<f[m]<<endl;return 0;
}

完全背包问题

定义：每种物品都有无限件可用。

一维结论是for(int j=m;j>= v[i];j–){这里面是正向for(int j=v[i] ;j<=m;j++)

01背包区别：f[i] [j] = max(f[i-1] [j] , f[i-1] [j-v[i]] +w[i])

完全背包区别：f[i] [j] = max(f[i-1] [j] ,f[i] [j-v[i]] +w[i])

#include<bits/stdc++.h>
using namespace std;
const int MAXX = 1010;
int f[MAXX];
int v[MAXX];
int w[MAXX];
int main(){int n,m;cin>>n>>m;for(int i=0; i<n; i++){cin>>v[i]>>w[i];}for(int i=0;i<n;i++){for(int j=v[i];j<=m;j++){//这里正序f[j] = max(f[j],f[j-v[i]] + w[i]);}}cout<<f[m]<<endl;return 0;
}

在这里插入图片描述

动态规划基础版本（空间优化版本）题解相似

题目：爬楼梯（斐波那契数）

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
示例 1：
输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶
示例 2：
输入：n = 3
输出：3
解释：有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶

思路： 要么在n-1个台阶上，结果是n-1的方案数，要么要么在n-1个台阶上，结果是n-2的方案数；两个方案数量和就是结果；f1是上一个状态 f0是上上一个状态
在这里插入图片描述

class Solution {
public:int climbStairs(int n) {int f0 =1, f1 = 1;for(int i = 2; i<= n ;i ++){int  f_res = f1 + f0;f0 = f1;f1 = f_res;}return f1;}
};

题目：使用最小花费爬楼梯

给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。
你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。
请你计算并返回达到楼梯顶部的最低花费。
示例 1：
输入：cost = [1,100,1,1,1,100,1,1,100,1]
输出：6
解释：你将从下标为 0 的台阶开始。

支付 1 ，向上爬两个台阶，到达下标为 2 的台阶。
支付 1 ，向上爬两个台阶，到达下标为 4 的台阶。
支付 1 ，向上爬两个台阶，到达下标为 6 的台阶。
支付 1 ，向上爬一个台阶，到达下标为 7 的台阶。
支付 1 ，向上爬两个台阶，到达下标为 9 的台阶。
支付 1 ，向上爬一个台阶，到达楼梯顶部。
总花费为 6 。
思路：
//fn = min( fn-1 | fn-2 + cost[n] )
//要解决的问题：dfs(i) 0或1 爬到i的最小花费
//枚举分类：
// 最后爬1个dfs(i) = dfs(i-1) +cost[i-1]
// 最后爬2个 dfs(i) = dfs(i-2) +cost[i-2]
//边界 dfs(0) =0或dfs(1) =0 爬到0或1 无需花费

//f1:上一个状态
//f0:上上一个状态
//新的状态newF = min(f1 + cost[i-1],f0 + cost[i-2])

class Solution {
public:int minCostClimbingStairs(vector<int>& cost) {int f0 = 0,f1 = 0;int len = cost.size();if(len == 0 | len == 1) return 0;for(int i=2; i <= len; i++){int newF = min(f1 + cost[i-1] ,f0 + cost[i-2]);f0 = f1;f1 = newF;}return f1;}
};

题目：打家劫舍

给定一个代表每个房屋存放金额的非负整数数组，计算你不触动警报装置的情况下（如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。），一夜之内能够偷窃到的最高金额。
输入：[2,7,9,3,1]
输出：12
解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
偷窃到的最高金额 = 2 + 9 + 1 = 12 。

class Solution {
public:int rob(vector<int>& nums) {int f0 = 0,f1 = 0;//只有一家的时候不能偷for(auto num : nums){int newF = max(f1 , f0 + num);f0 = f1;f1 = newF;}return f1;}
};
//最后一个选不选的问题
//fn 最高金额 = max （f1  ｜ f0 + nums[n])
//上一个状态 f1 
//上上状态 f0

题目：删除并获得点数

给你一个整数数组 nums ，你可以对它进行一些操作。
每次操作中，选择任意一个 nums[i] ，删除它并获得 nums[i] 的点数。之后，你必须删除所有等于 nums[i] - 1 和 nums[i] + 1 的元素。
开始你拥有 0 个点数。返回你能通过这些操作获得的最大点数。
示例 1：
输入：nums = [3,4,2]
输出：6
解释：
删除 4 获得 4 个点数，因此 3 也被删除。
之后，删除 2 获得 2 个点数。总共获得 6 个点数。
示例 2：
输入：nums = [2,2,3,3,3,4]
输出：9
解释：
删除 3 获得 3 个点数，接着要删除两个 2 和 4 。
之后，再次删除 3 获得 3 个点数，再次删除 3 获得 3 个点数。
总共获得 9 个点数。

**思路：*重点在于题目的转化，此题相当于对哈希表进行打家劫舍，其中的哈希表里面存的是数组里面数字出现的次数 数字（也就是累加）

//哈希表长度最大10^4 +1 （这里面可以直接设置MAXN 也可以用nums的最大值）
//哈希表存储累计的数字个数*下标
//然后对哈希表进行打家劫舍就能求出最大点数量
（这题一开始运行时间有点长）因为用了哈希map，后来想想思想都一样map换成vector，果然运行时间缩短了。。。。
在这里插入图片描述

class Solution {
public:int deleteAndEarn(vector<int>& nums) {int maxValue = 0;for(int i=0; i < nums.size(); i++){maxValue = max(maxValue,nums[i]);}vector<int> v1(maxValue+1);for(int i=0; i < nums.size(); i++){v1[nums[i]] += nums[i];}//打家劫舍int f0 = 0,f1 = 0;int newF = f0+f1;for(auto num : v1){newF = max(f0 + num, f1);f0 = f1;f1 = newF;}return f1;}
};