poj1163 The Triangle —

poj1163 The Triangle ——DP入门题

题目思路：

　　从三角形的底部开始考虑

 1 #include <iostream>
 2 #include <cstdlib>
 3 #include <cstring>
 4 #include <algorithm>
 5 #include <cstdio>
 6 using namespace std;
 7 const int MAX = 100;
 8 int a[MAX][MAX], dp[MAX][MAX];
 9 int main(void) {
10   //freopen("1163.in", "r", stdin);
11   int n,i,j; scanf("%d",&n);
12   for (i = 0; i < n; ++i) {
13     for (j = 0; j < i+1; ++j) {
14       scanf("%d", &a[i][j]);
15     }
16   }
17   memset(dp, 0, sizeof(dp));
18   for (i = 0; i < n; ++i) dp[n-1][i] = a[n-1][i];
19   for (i = n - 2; i >= 0; --i) {
20     for (j = 0; j < n - 1; ++j) {
21       dp[i][j] = max(dp[i+1][j], dp[i+1][j+1]) + a[i][j];
22     }
23   }
24   printf("%d\n", dp[0][0]);
25   return 0;
26 }

还是从最简单的开始做起吧

另外一种写法：

 1 #include <iostream>
 2 #include <cstdlib>
 3 #include <cstring>
 4 #include <algorithm>
 5 #include <cstdio>
 6 using namespace std;
 7 const int MAX = 100;
 8 int a[MAX][MAX], dp[MAX][MAX], n;
 9 int f(int i, int j) {
10   if (dp[i][j] >= 0) return dp[i][j];
11   else {
12     if (i == n-1) dp[i][j] = a[i][j];
13     else dp[i][j] = a[i][j] + max(dp[i+1][j], dp[i+1][j+1]);
14     return dp[i][j];
15   }
16 }
17 int main(void) {
18   int i,j; scanf("%d",&n);
19   for (i = 0; i < n; ++i) {
20     for (j = 0; j < i+1; ++j) {
21       scanf("%d", &a[i][j]);
22     }
23   }
24   memset(dp, -1, sizeof(dp));
25   for (i = 0; i < n; ++i) dp[n-1][i] = a[n-1][i];
26   for (i = n-1; i >= 0; --i)
27     for (j = 0; j < i+1; ++j)
28       f(i, j);
29   printf("%d\n", dp[0][0]);
30   return 0;
31 }

这就是所谓的记忆化搜索