算法-动态规划-数字三角问题


 1 #include <iostream>
 2 
 3 using namespace std;
 4 int Max(int a,int b)
 5 {
 6     return a>b?a:b;
 7 }
 8 int main()
 9 {   int a[10][10];
10     int n;
11     cout<<"输入行数"<<endl;
12     cin>>n;
13     cout<<"输入元素"<<endl;
14     for(int i=1;i<=n;i++)
15     {
16         for(int j=1;j<=i;j++)
17         {
18             cin>>a[i][j];
19         }
20     }
21     int b[10][10];
22     b[10][10]={0};
23     for(int j=1;j<=n;j++)
24     {
25         b[n][j]=a[n][j];
26     }
27     for(int i=n-1;i>=1;i--)//从倒数第二行开始
28     {
29         for(int j=1;j<=n;j++)
30         {
31            b[i][j]=Max(a[i][j]+b[i+1][j],a[i][j]+b[i+1][j+1]);
32         }
33     }
34     cout << b[1][1] << endl;
35     return 0;
36 }