1730数字三角形问题（DP）

 1 #include <iostream>
 2 #include <stdio.h>
 3 #include <string>
 4 #include <string.h>
 5 #include <algorithm>
 6 #include <math.h>
 7 #include <map>
 8 #include <vector>
 9 
10 #define inf 0x3f3f3f3f
11 
12 using namespace std;
13 
14 int main()
15 {
16     int n, i, j;
17     int a[105][105], dp[105][105];
18     cin >> n;
19     for(i=0;i<n;i++)
20     {
21         for(j=0;j<=i;j++)
22         {
23             cin >> a[i][j];
24         }
25     }
26     for(i=0;i<n;i++)
27     {
28         dp[n-1][i] = a[n-1][i];
29     }
30     for(i=n-2;i>=0;i--)
31     {
32         for(j=0;j<=i;j++)
33         {
34             dp[i][j] = a[i][j] + max(dp[i+1][j], dp[i+1][j+1]);
35         }
36     }
37     cout << dp[0][0] << endl;
38     return 0;
39 }