动态规划--备考蓝桥杯版h（史上无敌版）

动态规划就是递推的子集动态规划入门dfs暴力解决--记忆化搜索--递推动态规划练习1因为我们可以知道到达x的方案数肯定是取决于上一步是走两步还是走一步所以当我们用dfs进行枚举时就要考虑两种情况走一步与走两步然后再转化为有返回值的bfs时考虑dfs的含义是求方案数而在某点的方案数就是上一步走以一个台阶上一步走两个台阶然后在进行记忆化存储防止超时这样我们就可以很清晰的看出来动态规划该去怎样做这道题目了练习2暴力解决--每个位置选和不选类似指数型枚举--》不想实现记忆化数组版因为如果想要实现记忆化数组--》尽量保持传入的参数尽可能少#includeiostream #includecstring #includealgorithm using namespace std; const int N100010; typedef long long ll; int t; int n; int a[N]; ll res0; void dfs(int x,ll sum,int pos) { if(xn) { resmax(res,sum); return; } dfs(x1,sum,pos); if(pos1!x||pos0) { dfs(x1,suma[x],x); } } int main() { cint; while(t--) { cinn; for(int i1;in;i) { cina[i]; } res0; dfs(1,0,0); coutresendl; } return 0; }想实现记忆化数组版--》dfs暴力搜索参数极简版#includeiostream #includecstring #includealgorithm using namespace std; const int N100010; typedef long long ll; int t; int n; int a[N]; ll res0; int dfs(int x) { if(xn)return 0; else return max(dfs(x1),dfs(x2)a[x]); } int main() { cint; while(t--) { cinn; for(int i1;in;i) { cina[i]; } res0; resdfs(1); coutresendl; } return 0; }转化为有返回值的dfs记忆化搜索--在这个时候一定要知道搞明白返回的究竟是什么这里返回的值应该是截止到x的最大方案数那么我们可以根据一个样例画出递归树再根据递归树便可以得到递归方程进行动态规划的做法#includeiostream #includecstring #includealgorithm using namespace std; const int N100010; typedef long long ll; int t; int n; int a[N]; int mem[N]; ll res0; int dfs(int x) { if(mem[x]!-1)return mem[x]; int sum0; if(xn)return 0; else summax(dfs(x1),dfs(x2)a[x]); return mem[x]sum; } int main() { cint; while(t--) { cinn; for(int i1;in;i) { cina[i]; } res0; memset(mem,-1,sizeof mem); resdfs(1); coutresendl; } return 0; }扩展到动态规划注意我们是从底开始向上的所以是倒序#includeiostream #includecstring #includealgorithm using namespace std; const int N100010; typedef long long ll; int t; int n; int a[N]; int dp[N]; ll res0; int main() { cint; while(t--) { cinn; for(int i1;in;i) { cina[i]; } memset(dp,0,sizeof dp); for(int in;i1;i--) { dp[i]max(dp[i1],dp[i2]a[i]); } coutdp[1]endl; } return 0; }练习3P1216 [IOI 1994 / USACO1.5] 数字三角形 Number Triangles - 洛谷#includeiostream #includecstring #includealgorithm using namespace std; const int N1010; int n; int a[N][N]; int dp[N][N]; int main() { cinn; for(int i1;in;i) { for(int j1;ji;j) { cina[i][j]; } } for(int in;i1;i--) { for(int j1;ji;j) { dp[i][j]max(dp[i1][j],dp[i1][j1])a[i][j]; } } coutdp[1][1]endl; return 0; }背包问题0-1背包问题背包问题--》其实就是dfs搜索里面的选还是不选问题嘛所以当按照这个来做的时候就得到如下代码#includeiostream #includecstring #includealgorithm using namespace std; const int N1010; int n,V; int v[N],w[N]; int res0; void dfs(int x,int sum,int remain) { if(remain0)return; if(xn) { if(remain0) { resmax(res,sum); } return; } dfs(x1,sum,remain); if(remainv[x]) { dfs(x1,sumw[x],remain-v[x]); } } int main() { cinnV; for(int i1;in;i) { cinv[i]w[i]; } dfs(1,0,V); coutresendl; return 0; }但是这个是不方便用来记忆化搜索的因为这样的话就变成了三维数组--》#includeiostream #includecstring #includealgorithm using namespace std; const int N1010; int n,V; int v[N],w[N]; int res0; int dfs(int x,int remain) { if(xn)return 0; int ansdfs(x1,remain); if(remainv[x]) { return max(ans,dfs(x1,remain-v[x])w[x]); } else return ans; } int main() { cinnV; for(int i1;in;i) { cinv[i]w[i]; } resdfs(1,V); coutresendl; return 0; }接下来就是要完成记忆化搜索#includeiostream #includecstring #includealgorithm using namespace std; const int N1010; int n,V; int v[N],w[N]; int res0; int mem[N][N]; int dfs(int x,int remain) { if(mem[x][remain])return mem[x][remain]; if(xn)return 0; int ansdfs(x1,remain); if(remainv[x]) { ansmax(ans,dfs(x1,remain-v[x])w[x]); } return mem[x][remain]ans; } int main() { cinnV; for(int i1;in;i) { cinv[i]w[i]; } resdfs(1,V); coutresendl; return 0; }最后在进阶到动态规划解决很简单可以看出来由下往上的话可以得到递推关系式if(remainv[i])dp[i][remain]dp[i1][remain];else dp[i][remain]max(dp[i1][remain],dp[i1][remain]w[i]);#includeiostream #includecstring #includealgorithm using namespace std; const int N1010; int n,V; int v[N],w[N]; int res0; int dp[N][N]; int main() { cinnV; for(int i1;in;i) { cinv[i]w[i]; } for(int in;i1;i--) { for(int j0;jV;j) { if(jv[i]) { dp[i][j]dp[i1][j]; } else dp[i][j]max(dp[i1][j],dp[i1][j-v[i]]w[i]); } } coutdp[1][V]endl; return 0; }完全背包问题每个物品可以取无限次区间dp练习1最基础的dfs考虑选与不选枚举所有子序列void dfs(int x,int len) { if(xn) { if(check(len)) { resmax(res,len); } return; } //buxuan dfs(x1,len); //xuan path[x]s[x]; dfs(x1,len1); path[x]0; }然后我们通过题目当中的回文--》前后加上记忆化搜索得到如下解决#includeiostream #includealgorithm #includecstring using namespace std; const int N1010; string s; int n; int mem[N][N]; int dp[N][N]; int dfs(int i,int j) { if(mem[i][j]!-1)return mem[i][j]; if(ij)return 0; if(ij)return 1; int res0; if(s[i]s[j]) { resdfs(i1,j-1)2; } else { resmax(dfs(i1,j),dfs(i,j-1)); } return mem[i][j]res; } int main() { cins; ns.length(); memset(mem,-1,sizeof mem); coutdfs(0,n-1); return 0; }再转为区间dp即可得到#includeiostream #includealgorithm #includecstring using namespace std; const int N1010; string s; int n; int mem[N][N]; int dp[N][N]; int main() { cins; ns.length(); for(int i0;in;i) { dp[i][i]1; } for(int len2;lenn;len) { for(int i0;ilen-1n;i) { int jilen-1; if(s[i]s[j]) { dp[i][j]dp[i1][j-1]2; } else { dp[i][j]max(dp[i1][j],dp[i][j-1]); } } } coutdp[0][n-1]endl; return 0; }练习2P1775 石子合并弱化版 - 洛谷合并相邻石子最小总代价--》最后一次合并一定是两堆合并--》区间DP处理连续区间的最优值--》dp[i][j] 合并[i,j]的最小代价--》枚举最后一次合并的位置k--》dp[i][j] min(dp[i][k] dp[k1][j] sum[i][j])#includeiostream #includecstring #includealgorithm using namespace std; const int N1010; int n; int m[N]; int s[N]; int dp[N][N]; int main() { cinn; for(int i1;in;i) { cinm[i]; s[i]s[i-1]m[i]; } memset(dp,0x3f,sizeof dp); for(int i1;in;i) { dp[i][i]0; } for(int len2;lenn;len) { for(int i1;ilen-1n;i) { int jilen-1; for(int ki;kj;k) { int cosdp[i][k]dp[k1][j](s[j]-s[i-1]); dp[i][j]min(dp[i][j],cos); } } } coutdp[1][n]endl; return 0; }练习--树形dpP1352 没有上司的舞会 - 洛谷对于每个节点u定义dp[u][0]不选u时以u为根的子树的最大快乐值dp[u][1]选u时以u为根的子树的最大快乐值状态转移如果选udp[u][1] a[u] sum(dp[v][0])孩子都不能选如果不选udp[u][0] sum(max(dp[v][0], dp[v][1]))孩子可选可不选#includeiostream #includecstring #includealgorithm #includevector using namespace std; const int N6010; int n; int a[N]; vectorint child[N]; int dp[N][2]; bool havefa[N]; void dfs(int u) { dp[u][1]a[u];//xuan dp[u][0]0;//buxuan for(int i0;ichild[u].size();i) { int vchild[u][i]; dfs(v); dp[u][1]dp[v][0]; dp[u][0]max(dp[v][0],dp[v][1]); } } int main() { cinn; for(int i1;in;i) { cina[i]; } for(int i1;in;i) { int l,k; cinlk; child[k].push_back(l); havefa[l]true; } int root1; for(int i1;in;i) { if(!havefa[i]) { rooti; } } dfs(root); coutmax(dp[root][0],dp[root][1])endl; return 0; }练习题单蓝桥杯省十天冲刺省一(C版) - DashOJ新手动态规划合集 - 题单 - 洛谷 | 计算机科学教育新生态