洛谷[P1216]数字三角形 Number Triangles

洛谷[P1216] 数字三角形 Number Triangles

题目链接：数字三角形

一、递归 首先最容易想到的肯定是递归。

#include <iostream> #include <algorithm> #define MAX 1001 using namespace std; int D[MAX][MAX],n; int MaxSum(int i,int j) { if(i==n) return D[i][j]; int x=MaxSum(i+1,j); int y=MaxSum(i+1,j+1); return max(x,y)+D[i][j]; } int main() { int i,j; cin>>n; for(i=1;i<=n;i++) for(j=1;j<=i;j++) cin>>D[i][j]; cout<<MaxSum(1,1)<<endl; return 0; }

然而这种方法并不可行，对于n(1<=n<=1000)，肯定超时。 此程序中，D[1,1]（7）被MaxSum调用1次，D[2,1] (3)和D[2,2] (8)各被调用1次，而D[3,2] (1)被调用2次(D[2,1]和D[2,2])，D[4,2] (7)被D[3,1]（8）和D[3,2]（1）调用（总计3次）。以此类推，总共调2＾0+2＾1+2＾2+……+2＾(n-1)=2＾n次。时间复杂度是巨大的，即使到宇宙毁灭也算不出来。

二、记忆递归型动归

#include <iostream> #include <algorithm> using namespace std; #define MAX 1001 int D[MAX][MAX],n; int maxSum[MAX][MAX]; int MaxSum(int i,int j) { if(maxSum[i][j]!=-1) return maxSum[i][j]; if(i==n) maxSum[i][j]=D[i][j]; else { int x=MaxSum(i+1,j); int y=MaxSum(i+1,j+1); maxSum[i][j]=max(x,y)+D[i][j]; } return maxSum[i][j]; } int main() { int i,j; cin>>n; for(i=1;i<=n;i++) for(j=1;j<=i;j++) { cin>>D[i][j]; maxSum[i][j]=-1; } cout<<MaxSum(1,1)<<endl; return 0; }

三、递推型动态规划（典型动态规划） 从下往上推，二维数组对应位置存储由下往上推到当前位置时更大的那个结果。 可以看到，对应位置的结果只与上一步推的结果和当前位置的初始值有关。由此可得状态转移方程：maxSum[i][j]=max(maxSum[i+1][j],maxSum[i+1][j+1])+D[i][j]。

#include <iostream> #include <algorithm> using namespace std; #define MAX 1001 int D[MAX][MAX],n; int maxSum[MAX][MAX]; int main() { int i,j; cin>>n; for(i=1;i<=n;i++) for(j=1;j<=i;j++) cin>>D[i][j]; for(i=1;i<=n;i++) maxsum[n][i]=D[n][i];//底部初始化 for(i=n-1;i>=1;i--) for(j=1;j<=i;j++) maxSum[i][j]=max(maxSum[i+1][j],maxSum[i+1][j+1])+D[i][j]; cout<<maxSum[1][1]<<endl; return 0; }

空间优化（1） 由于二维数组当前行的状态的值确定后，就和下面一行的值无关，因此可以用一维数组存储即可，最后输出maxSum[1]。

#include <iostream> #include <algorithm> using namespace std; #define MAX 1001 int D[MAX][MAX],n,maxSum[MAX]; int main() { int i,j; cin>>n; for(i=1;i<=n;i++) for(j=1;j<=i;j++) cin>>D[i][j]; for(i=1;i<=n;i++) maxSum[i]=D[n][i];//底部初始化 for(i=n-1;i>=1;i--) for(j=1;j<=i;j++) maxSum[j]=max(maxSum[j],maxSum[j+1])+D[i][j]; cout<<maxSum[1]<<endl; return 0; }

空间优化（2）

#include <iostream> #include <algorithm> using namespace std; #define MAX 1001 int D[MAX][MAX],n; int *maxSum; int main() { int i,j; cin>>n; for(i=1;i<=n;i++) for(j=1;j<=i;j++) cin>>D[i][j]; for(i=1;i<=n;i++) maxSum=D[n];//底部初始化 for(i=n-1;i>=1;i--) for(j=1;j<=i;j++) maxSum[j]=max(maxSum[j],maxSum[j+1])+D[i][j]; cout<<maxSum[1]<<endl; return 0; }