hihocoder1037 数字三角形

数字三角形是一个典型的DP问题。

下面是分别采用记忆化bfs和DP的代码：

采用记忆化bfs：

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <queue>
 4 #include <algorithm>
 5 using namespace std;
 6 
 7 #define MAXN 201
 8 
 9 int prize[MAXN][MAXN];
10 int res[MAXN][MAXN];
11 bool isInQ[MAXN][MAXN];
12 int n, ans;
13 
14 struct node
15 {
16     int i, j;
17     node(int _i, int _j):i(_i),j(_j){}
18 };
19 
20 void bfs()
21 {
22     queue<node> q;
23     q.push(node(1, 1));
24     memset(isInQ, 0, sizeof(isInQ));
25     isInQ[1][1] = 1;
26     while(!q.empty())
27     {
28         node nd = q.front();
29         q.pop();
30         if(nd.i==1&&nd.j==1)
31         {
32             res[1][1] = prize[1][1];
33         }
34         else
35         {
36             res[nd.i][nd.j] = max(res[nd.i-1][nd.j-1], res[nd.i-1][nd.j])+prize[nd.i][nd.j];
37         }
38         if(nd.i<n)
39         {
40             if(!isInQ[nd.i+1][nd.j]) q.push(node(nd.i+1, nd.j));
41             if(!isInQ[nd.i+1][nd.j+1]) q.push(node(nd.i+1, nd.j+1));
42             isInQ[nd.i+1][nd.j] = isInQ[nd.i+1][nd.j+1] = 1;
43         }
44     }
45     ans = 0;
46     for(int i=1; i<=n; ++i) ans = max(ans, res[n][i]);
47 }
48 
49 int main()
50 {
51     while(scanf("%d", &n)!=EOF)
52     {
53         for(int i=1; i<=n; ++i)
54             for(int j=1; j<=i; ++j)
55                 scanf("%d", &prize[i][j]);
56         bfs();
57         printf("%d
", ans); 
58     }
59     return 0;
60 }

采用DP：

 1 #include <cstdio>
 2 #include <algorithm>
 3 using namespace std;
 4 
 5 #define MAXN 201
 6 
 7 int prize[MAXN][MAXN];
 8 int dp[MAXN][MAXN];
 9 
10 int main()
11 {
12     int n, ans;
13     while(scanf("%d", &n)!=EOF)
14     {
15         for(int i=1; i<=n; ++i)
16             for(int j=1; j<=i; ++j)
17                 scanf("%d", &prize[i][j]);
18         dp[1][1] = prize[1][1];
19         for(int i=1; i<=n; ++i) dp[i][0] = 0;
20         for(int i=2; i<=n; ++i)
21         {
22             for(int j=1; j<=i; ++j)
23                 dp[i][j] = max(dp[i-1][j-1], dp[i-1][j])+prize[i][j];
24         }
25         ans = 0;
26         for(int i=1; i<=n; ++i) ans = max(ans, dp[n][i]);
27         printf("%d
", ans);
28     }
29     return 0;
30 }

题目来源：http://hihocoder.com/problemset/problem/1037