学习dp入门
动态规划入门思路：dfs暴力--》记忆化搜索--》递推
跳台阶
可以先把递归的图先画出来
因为我们的dfs是去从5递推的去
dfs就是从下面往上推回去
dfs
#include<bits/stdc++.h>#define int long long
#define endl '\n'int n;using namespace std;
int dfs(int x){if(x==1)return 1;if(x==2)return 2;else return dfs(x-1)+dfs(x-2);
}
signed main(){std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin>>n;int res=dfs(n);cout<<res<<endl;return 0;
}
但是我们发现好像有的地方会去重复，我们是不是可以用一个数组去存储这个值，到了递归到这里直接给出答案就行了。
dfs+记忆化搜索
#include<bits/stdc++.h>#define int long long
#define endl '\n'int n;
int mu[105]={0};//用这个来记忆以及走过的值
using namespace std;
int dfs(int x){if(mu[x])return mu[x];int sum=0;if(x==1)sum=1;else if(x==2)sum=2;else sum=dfs(x-1)+dfs(x-2);mu[x]=sum;return sum;
}signed main(){std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin>>n;int res=0;res=dfs(n);cout<<res<<endl;return 0;
}
dp求解
我们可以直接归，从下面的问题直接到底说明的问题
#include<bits/stdc++.h>#define int long long
#define endl '\n'int n;
int mu[105]={0};
int dp[105];
using namespace std;
//int dfs(int x){
// if(mu[x])return mu[x];
// int sum=0;
// if(x==1)sum=1;
// else if(x==2)sum=2;
// else sum=dfs(x-1)+dfs(x-2);
// mu[x]=sum;
// return sum;
//}signed main(){std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin>>n;//初始化dp[1]=1;dp[2]=2;if(n==1||n==2){cout<<dp[n]<<endl;} for(int i=3;i<=n;i++){//状态转移 dp[i]=dp[i-1]+dp[i-2];} cout<<dp[n]<<endl;return 0;
}
也可以用滚动的方式交换位置就可以了
大盗阿福
题意就是偷金点不能连着去偷，只能有间隔的去偷；
画出流程树状图
dfs
#include<bits/stdc++.h>#define int long long
#define endl '\n'int n;
int m[109]={0};
int mu[105]={0};
int dp[105];
using namespace std;
int dfs(int x){if(x>n)return 0;else return max(dfs(x+1),dfs(x+2)+m[x]);
}signed main(){std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t;cin>>t;while(t--){cin>>n;for(int i=1;i<=n;i++){cin>>m[i];}int res=dfs(1);cout<<res<<endl;} return 0;
}
dfs+记忆化数组
用数组去存储记忆已经存在的东西
#include<bits/stdc++.h>#define int long long
#define endl '\n'int n;
int m[109]={0};
int mu[105]={0};
int dp[105];
using namespace std;
int dfs(int x){if(mu[x])return mu[x];int sum=0;if(x>n)sum=0;else sum=max(dfs(x+1),dfs(x+2)+m[x]);m[x]=sum;return sum;
}signed main(){std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t;cin>>t;while(t--){cin>>n;for(int i=1;i<=n;i++){cin>>m[i];}memset(mu,0,sizeof(mu));int res=dfs(1);cout<<res<<endl;} return 0;
}
dp加逆序递推
从图中可以看到，这个情况
和我们dfs开始写的一模一样从后面开始推回来
#include<bits/stdc++.h>#define int long long
#define endl '\n'int n;
int m[109]={0};
int mu[105]={0};
int dp[105];
using namespace std;
const int N=1e5+10;
//int dfs(int x){
// if(mu[x])return mu[x];
// int sum=0;
// if(x>n)sum=0;
// else sum=max(dfs(x+1),dfs(x+2)+m[x]);
// m[x]=sum;
// return sum;
//}
int f[N];signed main(){std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t;cin>>t;while(t--){cin>>n;for(int i=1;i<=n;i++){cin>>m[i];}memset(f, 0, sizeof f);for(int i=n;i>=1;i++){f[i] = max(f[i+1], f[i+2] + m[i]);}cout<<f[1]<<endl;} return 0;
}
dp加顺序递推
这个就要去考虑要去初始化了
#include<bits/stdc++.h>#define int long long
#define endl '\n'int n;
int m[109]={0};
int mu[105]={0};
int dp[105];
using namespace std;
const int N=1e5+10;
//int dfs(int x){
// if(mu[x])return mu[x];
// int sum=0;
// if(x>n)sum=0;
// else sum=max(dfs(x+1),dfs(x+2)+m[x]);
// m[x]=sum;
// return sum;
//}
int f[N];signed main(){std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t;cin>>t;while(t--){cin>>n;for(int i=1;i<=n;i++){cin>>m[i];}memset(f, 0, sizeof f);f[0]=0;f[1]=m[1];for(int i=2;i<=n;i++){f[i] = max(f[i-1], f[i-2] + m[i]);}cout<<f[n]<<endl;} return 0;
}
01背包
题目
n个物品，体积v[i]，价值w[i]，背包容量V，求最大价值（每个物品只能选一次）
dfs
#include<bits/stdc++.h>
#define int long long
using namespace std;const int N = 105;int n, V;
int v[N], w[N];// dfs(i, j) = 从前i个物品中选，剩余容量为j，能获得的最大价值
int dfs(int i, int j) {if(i == 0) return 0; // 没有物品了// 选择1：不选第i个物品int skip = dfs(i - 1, j);// 选择2：选第i个物品（容量够才能选）int steal = 0;if(j >= v[i]) {steal = w[i] + dfs(i - 1, j - v[i]);}return max(skip, steal);
}signed main() {ios::sync_with_stdio(false);cin.tie(0);cin >> n >> V;for(int i = 1; i <= n; i++) cin >> v[i] >> w[i];cout << dfs(n, V) << endl;return 0;
}
dfs加记忆化搜索
#include<bits/stdc++.h>
#define int long long
using namespace std;const int N = 105;int n, V;
int v[N], w[N];
int memo[N][1005]; // 记忆化数组，-1表示未计算int dfs(int i, int j) {if(i == 0) return 0;if(memo[i][j] != -1) return memo[i][j]; // 查缓存// 不选int skip = dfs(i - 1, j);// 选int steal = 0;if(j >= v[i]) {steal = w[i] + dfs(i - 1, j - v[i]);}return memo[i][j] = max(skip, steal); // 存缓存
}signed main() {ios::sync_with_stdio(false);cin.tie(0);memset(memo, -1, sizeof memo); // 初始化为-1cin >> n >> V;for(int i = 1; i <= n; i++) cin >> v[i] >> w[i];cout << dfs(n, V) << endl;return 0;
}
正序DP（递推）
#include<bits/stdc++.h>
#define int long long
using namespace std;const int N = 105;
const int M = 1005;int n, V;
int v[N], w[N];
int f[N][M]; // f[i][j] = 前i个物品，容量j的最大价值signed main() {ios::sync_with_stdio(false);cin.tie(0);cin >> n >> V;for(int i = 1; i <= n; i++) cin >> v[i] >> w[i];// 初始化：f[0][j] = 0（前0个物品价值为0）for(int i = 1; i <= n; i++) { // 枚举物品for(int j = 0; j <= V; j++) { // 枚举容量// 不选第i个f[i][j] = f[i-1][j];// 选第i个（容量够）if(j >= v[i]) {f[i][j] = max(f[i][j], f[i-1][j-v[i]] + w[i]);}}}cout << f[n][V] << endl;return 0;
}
逆序DP
#include<bits/stdc++.h>
#define int long long
using namespace std;const int N = 105;
const int M = 1005;int n, V;
int v[N], w[N];
int f[N][M]; // f[i][j] = 从第i个到第n个，剩余容量j的最大价值signed main() {ios::sync_with_stdio(false);cin.tie(0);cin >> n >> V;for(int i = 1; i <= n; i++) cin >> v[i] >> w[i];// 初始化：f[n+1][j] = 0（后面没有物品了）for(int i = n; i >= 1; i--) { // 逆序枚举物品for(int j = 0; j <= V; j++) { // 枚举容量// 不选第i个，去i+1f[i][j] = f[i+1][j];// 选第i个，去i+1，容量减少if(j >= v[i]) {f[i][j] = max(f[i][j], f[i+1][j-v[i]] + w[i]);}}}cout << f[1][V] << endl; // 从第1个开始，容量Vreturn 0;
}