动态规划和回溯总结
一、总结
一句话总结:
算法的录课可以以大知识点为一门课程,比如dp,比如回溯,比如线段树,比如最短路等等
1、动态规划技巧总结?
1、找准状态:一般问题所问我们就可以设置为状态
2、找变化(转移)关系:也就是找递推表达式:也就是找动态规划的状态转移方程
3、找好起始状态和最终状态
4、找好刷表的顺序:也就是每层循环的实际意义
2、动态规划的核心?
1、空间换时间
2、刷表(也就是依次把表填起来)
3、动态规划技巧--数字金字塔实例(求顶到底最大路径和)?
1、找准状态:求顶到底最大路径和:f[i][j]表示从顶点到第i行第j列的路径和最大值
2、找变化(转移)关系-【递推表达式】【状态转移方程】:到f[i][j]位置只能由f[i-1][j]和f[i-1][j-1]:f[i][j]=max(f[i-1][j],f[i-1][j-1])+A[i][j]
3、找好起始状态和最终状态:起始状态就是顶点f[1][1],最终状态就是max(f[n][j])
4、找好刷表的顺序:也就是每层循环的实际意义:行由上到下(i...1->n),列由左到由(j...1->i)
5
13
11 8
12 7 26
6 14 15 8
12 7 13 24 11
4、回溯做题思路总结?
a、回溯就是题目的描述是怎么,你直接简单粗暴的照着描述写回溯就好,比如数字金字塔是求顶到底最大路径和,那么你直接顶到底这样逐层回溯就好,可深搜,也可广搜,
b、回溯优化的话记得剪枝和记忆化递归(保存中间状态)
c、回溯讲的话可以画出决策树
5、回溯思路---数字金字塔(求顶到底最大路径和)?
回溯就是题目的描述是怎么,你直接简单粗暴的照着描述写回溯就好,比如数字金字塔是求顶到底最大路径和,那么你直接顶到底这样逐层回溯就好,可深搜,也可广搜,
5
13
11 8
12 7 26
6 14 15 8
12 7 13 24 11
6、回溯如何求最短路?
最短路也就是点到点的最短距离,那我就按照题目描述从点到点回溯即可,递归就是每一个点的选择情况
7、回溯求素数环--从1到20这20个数摆成一个环,要求相邻的两个数的和是一个素数?
a、条件:相邻两个数构成素数,并且数没有被用(所以可以用一个数组来记录数是否被用了)
b、存储:一个数组存数有没有被用,一个数组存结果
c、递归:递归也就是每一个位置的取数情况:也就是每一个位置的选择情况
1 #include<cstdio> 2 #include<iostream> 3 #include<cstdlib> 4 #include<cmath> 5 using namespace std; 6 bool b[21]={0}; 7 int total=0,a[21]={0}; 8 int search(int); //回溯过程 9 int print(); //输出方案 10 bool pd(int,int); //判断素数 11 12 int main() 13 { 14 search(1); 15 cout<<total<<endl; //输出总方案数 16 } 17 int search(int t) 18 { 19 int i; 20 for (i=1;i<=20;i++) //有20个数可选 21 if (pd(a[t-1],i)&&(!b[i])) //判断与前一个数是否构成素数及该数是否可用 22 { 23 a[t]=i; 24 b[i]=1; 25 if (t==20) { if (pd(a[20],a[1])) print();} 26 else search(t+1); 27 b[i]=0; 28 } 29 } 30 int print() 31 { 32 total++; 33 cout<<"<"<<total<<">"; 34 for (int j=1;j<=20;j++) 35 cout<<a[j]<<" "; 36 cout<<endl; 37 } 38 bool pd(int x,int y) 39 { 40 int k=2,i=x+y; 41 while (k<=sqrt(i)&&i%k!=0) k++; 42 if (k>sqrt(i)) return 1; 43 else return 0; 44 }
8、回溯中的递归怎么写?
回溯中的递归也就是每一个位置的选择情况,拿素数环(1-20摆成素数环)来说,也就是每一个位置选择的20种情况
素数环:从1到20这20个数摆成一个环,要求相邻的两个数的和是一个素数。
9、动态规划技巧--01背包问题(物品n件,每件重量wi,价值vi,背包总大小V,求装物品使背包中物品价值最大)?
1、找准状态:求装n件物品的背包总价值最大:f[i][j]表示装i件物品的背包的总价值为j
2、找变化(转移)关系-【递推表达式】【状态转移方程】:第i件物品有装和不装两种选择:f[i][j]=max(f[i-1][j],f[i-1][j-wi]+vi)
3、找好起始状态和最终状态:起始状态就是没有物品价值也为0,f[0][0],最终状态就是max(f[n][j])
4、找好刷表的顺序:也就是每层循环的实际意义:行由上到下(i...0->n),列由左到由(j...0->j)
1 【解法一】设f[i][v]表示前i件物品,总重量不超过v的最优价值,则f[i][v]=max(f[i-1][v-w[i]]+c[i],f[i-1][v]) ;f[n][m]即为最优解,给出程序: 2 #include<cstdio> 3 using namespace std; 4 const int maxm = 201, maxn = 31; 5 int m, n; 6 int w[maxn], c[maxn]; 7 int f[maxn][maxm]; 8 9 int max(int x,int y) { x>y?x:y;} //求x和y最大值 10 11 int main(){ 12 scanf("%d%d",&m, &n); //背包容量m和物品数量n 13 for (int i = 1; i <= n; i++) //在初始化循环变量部分,定义一个变量并初始化 14 scanf("%d%d",&w[i],&c[i]); //每个物品的重量和价值 15 for (int i = 1; i <= n; i++) // f[i][v]表示前i件物品,总重量不超过v的最优价值 16 for (int v = m; v > 0; v--) 17 if (w[i] <= v) f[i][v] = max(f[i-1][v],f[i-1][v-w[i]]+c[i]); 18 else f[i][v] = f[i-1][v]; 19 printf("%d",f[n][m]); // f[n][m]为最优解 20 return 0; 21 }
10、动态规划 刷表的理解?
由已知的位置刷新未知的位置:由上一行(指定位置)更新下一行,比如没有优化的01背包,数字金字塔由左上和正上的格子刷新当前格子
二、内容在总结中
博客对应课程的视频位置: