时间戳

首页 > 技术文章 > 数字三角形从顶到底的最大路径和

数字三角形从顶到底的最大路径和

cynthia-dcg 2017-04-12 08:57 原文

问题描述：

           7

       3       8

   8       1        0

2      7       4          4

      在上面的数字三角形中寻找一条从顶部到底边的路径，使得路径上所经过的数字之和最大。路径上的每一步都只能往左下或右下走。只需要求出这个最大和即可，不必给出具体路径。

      三角形的行数大于1小于等于100，数字为0~99.

输入格式：

4 ///三角形的行数。下面是三角形

7

3 8

8 1 0

2 7 4 4

要求输出最大和

第一种方法：利用递归（超时，原因是重复计算，时间复杂度是2n）

 1 #include <iostream>
 2 #include <algorithm>
 3 #define Max 101
 4 using namespace std;
 5 int D[Max][Max];
 6 int n;
 7 int MaxSum(int i,int j)
 8 {
 9     if(i==n)
10         return D[i][j];
11     int x=MaxSum(i+1,j);
12     int y=MaxSum(i+1,j+1);
13     return max(x,y)+D[i][j];
14 }
15 int main()
16 {
17     int i,j;
18     cin>>n;
19     for(i=1;i<=n;i++)
20         for(j=1;j<=i;j++)
21     {
22         cin>>D[i][j];
23     }
24     cout<<MaxSum(1,1)<<endl;
25     return 0;
26 }

第二种方法是动态规划（用数组存放已经计算出来的值，避免重复计算，时间复杂度是n2）

 1 #include <iostream>
 2 #include <algorithm>
 3 using namespace std;
 4 #define Max 101
 5 int D[Max][Max];
 6 int n;
 7 int maxSum[Max][Max];
 8 int MaxSum(int i,int j)
 9 {
10     if(maxSum[i][j]!=-1)
11         return maxSum[i][j];
12     if(i==n)
13         maxSum[i][j]=D[i][j];
14     else
15     {
16         int x=MaxSum(i+1,j);
17         int y=MaxSum(i+1,j+1);
18         maxSum[i][j]=max(x,y)+D[i][j];
19     }
20     return maxSum[i][j];
21 }
22 int main()
23 {
24     int i,j;
25     cin>>n;
26     for(i=1;i<=n;i++)
27         for(j=1;j<=i;j++)
28     {
29         cin>>D[i][j];
30         maxSum[i][j]=-1;
31     }
32     cout<<MaxSum(1,1)<<endl;
33     return 0;
34 }

 第三种方法：递归改为递推，从底往上计算

 1 #include <iostream>
 2 #include <algorithm>
 3 using namespace std;
 4 #define Max 101
 5 int D[Max][Max];
 6 int n;
 7 int maxSum[Max][Max];
 8 int main()
 9 {
10     int i,j;
11     cin>>n;
12     for(i=1;i<=n;i++)
13     {
14         for(j=1;j<=i;j++)
15             cin>>D[i][j];
16     }
17     for(int i=1;i<=n;i++)
18         maxSum[n][i]=D[n][i];
19     for(int i=n-1;i>=1;i--)
20         for(int j=1;j<=i;j++)
21     {
22         maxSum[i][j]=max(maxSum[i+1][j],maxSum[i+1][j+1])+D[i][j];
23     }
24     cout<<maxSum[1][1]<<endl;
25     return 0;
26 }

第四种方法：进行空间优化 将二维数组转变为一维数组向上翻滚

 1 #include <iostream>
 2 #include <algorithm>
 3 using namespace std;
 4 #define Max 101
 5 int D[Max][Max];
 6 int n;
 7 int *maxSum;
 8 int main()
 9 {
10     int i,j;
11     cin>>n;
12     for(i=1;i<=n;i++)
13         for(j=1;j<=i;j++)
14     {
15         cin>>D[i][j];
16     }
17     maxSum=D[n];////maxSum指向第n行
18     for(int i=n-1;i>=1;i--)
19         for(int j=1;j<=i;j++)
20     {
21         maxSum[j]=max(maxSum[j],maxSum[j+1])+D[i][j];
22     }
23     cout<<maxSum[1]<<endl;
24     return 0;
25 }

第五种方法是直接利用D[n]代替int maxsum[n]
第二种方法到第五种方法的时间复杂度都是n*n。

 

推荐阅读