关于最大子序列与最大矩阵和的粗略理解

xiaoxiao2021-03-01  5

补了一天的DP,翻了很多很多的博客,总算是对最大子序列和最大矩阵有了一些自己的理解,在这里分享一下。

理论在这里不多提,一会儿直接上代码(C++):最大子序列以及最大子矩阵的DP理论 这里只提一点,就是最大子矩阵是由最大子序列演化而来,无非就是多了个枚举。

从网上的东西中大约可以看出两类,一类是简单版,一类是官方版。

所谓简单版就是运用DP的思想,用各式各样的方法解出结果,书写形式很多,但是核心仍然是DP; 所谓官方版就是严格按照DP的格式来书写,定义DP数组,DP函数。。。。。等等。

但是可以看出书写简单版的人无疑是对DP使用的炉火纯青,所以个人认为还是尽量去接触那种简单版的代码,因为DP的书写多种多样,按照固定的格式写局限性太多,个人感觉DP只是为你提供了一种优化思想,而不是提供了你一种可以去套的板子,所以还是尽量的去尝试去改变。

下面给出简单版和官方版的代码,希望都能好好理解这两种书写形式,共同进步:

//最大子区间 int a[maxn]; //简单版 int main() { int n; scanf("%d",&n); for(int i=0;i<n;i++) scanf("%d",&a[i]); int sum=-1,b=0; for(int i=0;i<n;i++) { if(b>=0) b+=a[i]; else b=a[i]; if(sum<=b) sum=b; } printf("%d\n",sum); return 0; } //官方版 int a[maxn],dp[maxn]; int main() { int n; scanf("%d",&n); for(int i=0;i<n;i++) scanf("%d",&a[i]); memset(dp,0,sizeof(dp)); int res=-1; dp[0]=a[0]; for(int i=1;i<n;i++) { if(dp[i-1]>=0) dp[i]+=a[i]+dp[i-1]; else dp[i]=a[i]; if(dp[i]>res) res=dp[i]; } printf("%d\n",res); return 0; } //最大子矩阵 //官方版 int a[maxn][maxn],dp[maxn],b[maxn]; int main() { int n,m; scanf("%d %d",&n,&m); for(int i=0;i<n;i++) for(int j=0;j<m;j++) scanf("%d",&a[i][j]); int res=-1; for(int i=0;i<n;i++) { memset(b,0,sizeof(b));//每次枚举都要清空 for(int j=i;j<n;j++)//枚举行 { for(int k=0;k<m;k++) { b[k]+=a[j][k];//b中储存每一列的值 } dp[0]=b[0]; for(int i=1;i<m;i++) { if(dp[i-1]>=0) dp[i]=b[i]+dp[i-1]; else dp[i]=b[i]; if(dp[i]>res) res=dp[i]; } } } printf("%d\n",res); return 0; } //简单版 int a[maxn][maxn],b[maxn]; int main() { int n,m; scanf("%d %d",&n,&m); for(int i=0;i<n;i++) for(int j=0;j<m;j++) scanf("%d",&a[i][j]); int res=-1; for(int i=0;i<n;i++) { memset(b,0,sizeof(b)); for(int j=i;j<n;j++) { for(int k=0;k<m;k++) { b[k]+=a[j][k]; } int t=0; for(int i=0;i<m;i++) { if(t>=0) t+=a[i][j]; else t=a[i][j]; if(res<t) res=t; } } } printf("%d\n",res); }

还是要再次说明,算法的最大意义是给你提供了这种思想,不要一味的死套 板子,要牢牢的将这种思想抓在手里。

转载请注明原文地址: https://www.6miu.com/read-4150132.html

最新回复(0)