算法注意---3、分治的本质
一、总结
一句话总结:
分治本质上还是枚举,只是和普通枚举的枚举方向不同,仅此而已
1、为什么包含mid的序列,转化成求出区间[i..mid]的最大值与区间[mid+1..j]的最大值也可?
包含mid的子序列分为【包含mid且包含mid+1】和【包含mid且不包含mid+1】,前者就是所求,后者是左边的序列
②跨越序列中间:i<=mid<=j<=r 求解 包含mid的子序列 ===> 即求出区间[i..mid]的最大值与区间[mid+1..j]的最大值,将其相加即可 (不仅包含的mid,还一定包含了mid+1) 包含mid的子序列: (包含mid且包含mid+1): (包含mid且不包含mid+1):直接就是左边的序列
2、递归的终止条件的意义?
递归的终止条件也就是问题最简情况的解,或者问题的初始解
递归做分治: a、递归的终止条件: 因为我们的递归是为了求l到r序列的子序列的最大值, 所以当区间只有一个元素时,就是终止条件,那个元素就是子序列的最大值 b、递归的递推表达式:比较方式1、2、3的最大值。第2种跨越mid值的需要我们去计算,1,3种情况又转化成了子问题 c、递归的返回值:子序列的最大和 ①完全处于序列的左半:l<=i<=j<=mid ②跨越序列中间:i<=mid<=j<=r ③完全处于序列的右半:mid<=i<=j<=r
3、我们常说的状态是什么,比如动态规划中?
比如动态规划中,状态其实是我们设的,这个状态可以是题目所求,也可以是和题目所求相关的
动态规划能够优化,是因为找准了状态之间的转移关系,并且存储了中间的状态,
减少了大量重复求状态的计算,所以动态规划一般效率非常高
4、代码层面优化的两个方向?
*、时间方面优化:循环可以合并(循环方向一致,循环最大值也是,并且两个循环之间没有什么逻辑操作代码)
*、空间方面优化:代码中只用到了a[i],所以a[]数组可以用一个变量来代替
#include <iostream> #include <algorithm> using namespace std; int a[200005]; int main(){ int n; cin>>n; for(int i=1;i<=n;i++){ cin>>a[i]; } int sum=a[1]; int maxx=a[1]; for(int i=2;i<=n;i++){ if(sum<=0) sum=0; sum+=a[i]; maxx=max(sum,maxx); } cout<<maxx<<endl; return 0; }
5、代码中循环什么情况下可以合并?
循环可以合并(循环方向一致,循环最大值也是,并且两个循环之间没有什么逻辑操作代码)
#include <iostream> #include <algorithm> using namespace std; int a[200005]; int main(){ int n; cin>>n; for(int i=1;i<=n;i++){ cin>>a[i]; } int sum=a[1]; int maxx=a[1]; for(int i=2;i<=n;i++){ if(sum<=0) sum=0; sum+=a[i]; maxx=max(sum,maxx); } cout<<maxx<<endl; return 0; }
6、代码中数组什么时候可以用一个变量来代替?
代码中只用到了a[i],所以a[]数组可以用一个变量来代替
#include <iostream> #include <algorithm> using namespace std; int a[200005]; int main(){ int n; cin>>n; for(int i=1;i<=n;i++){ cin>>a[i]; } int sum=a[1]; int maxx=a[1]; for(int i=2;i<=n;i++){ if(sum<=0) sum=0; sum+=a[i]; maxx=max(sum,maxx); } cout<<maxx<<endl; return 0; }
7、贪心和动态规划本质的区别?
-、最大字段和的贪心解法就是只考虑当前对于a[i]最优的情况,是选择s[i-1]还是不选择s[i-1]来得到局部最优解
-、最大字段和的动态规划解法就是在全局统筹的基础上,找到规律,通过规律设置好状态,找到状态转移的方程
最大连续子序列的和
8、动态规划找规律的本质?
动态规划解法就是在全局统筹的基础上,找到规律,通过规律设置好状态,找到状态转移的方程
9、滚动数组优化动态规划?
A、在最大字段和的动态规划的解法的代码中,我们发现用来做动态规划的数组f在代码中只用到了f[i]和f[i-1],所以我们可以用只有两个元素的滚动数组来优化f数组
B、int maxx=f[1];f[i%2]=max(f[!(i%2)]+x,x);
#include <iostream> #include <algorithm> using namespace std; int f[2]={0}; int main(){ int n; cin>>n; cin>>f[1]; //1、确定动态规划初始条件:f[1]=a[1] int maxx=f[1]; for(int i=2;i<=n;i++){ int x; cin>>x; //2、动态规划操作:f[i]=max(f[i-1]+a[i],a[i]) (2<=i<=n) f[i%2]=max(f[!(i%2)]+x,x); //3、求ans:Answer=max{f[i]|1<=i<=n} maxx=max(f[i%2],maxx); } cout<<maxx<<endl; return 0; }
10、分治的本质?
分治本质上还是枚举,只是和普通枚举的枚举方向不同,仅此而已
二、内容在总结中
博客对应课程的视频位置: