递归动态规划:
1 #include <iostream> 2 #include <cstring> 3 #include <algorithm> 4 using namespace std; 5 int D[10][10];//i,j位置的值 6 int n; 7 int maxSum[10][10]; 8 int MaxSum(int i,int j){ //i,j到底边的最大和 9 if(maxSum[i][j]!=-1) return maxSum[i][j]; 10 if(i==n){ 11 maxSum[i][j]=D[i][j]; 12 }else{ 13 int x=MaxSum[i+1][j]; 14 int y=MaxSum[i+1][j+1]; 15 maxSum[i][j]=max(x,y)+D[i][j]; 16 } 17 return maxSum[i][j]; 18 } 19 int main(){ 20 int i,j; 21 cin>>n; 22 for(i=1;i<n;i++){ 23 for(j=1;j<i;j++) 24 { 25 cin>>D[i][j]; 26 maxSum[i][j]=-1; 27 } 28 } 29 cout<<MaxSum(1,1); 30 31 }
递推动态规划:使用指针省略空间:
1 #include <iostream> 2 #include <algorithm> 3 using namespace std; 4 int D[10][10]; 5 int *maxSum; 6 int n; 7 int main(){ 8 cin>>n; 9 int i,j; 10 for(i=1;i<=n;i++) 11 { 12 for(j=1;j<=i;j++) 13 { 14 cin>>D[i][j]; 15 } 16 } 17 maxSum=D[n];//max指向数组最后一行 18 for(i=n-1;i>=1;i--) 19 { 20 for(j=1;j<=i;j++) 21 { 22 maxSum[j]=max(maxSum[j],maxSum[j+1])+D[i][j]; 23 } 24 } 25 cout<<maxSum[1]<<endl; 26 27 }