【hihoCoder】1037 : 数字三角形

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

一个迷宫有n层，第 i 层有 i 个房间
从第i层的第i个房间(i, i)可以走到第i+1层的第i个房间或第i+1房间(i+1, i)/(i+1, i+1)
每个房间走出去后都不能回头

样例输入

5 //迷宫的层数
2
6 4
1 2 8
4 0 9 6
6 5 5 3 6
结果： 28
思路
动态规划
maze[i, j] = max(maze[i-1, j], maze[i-1, j-1])

源码

迭代方式，从下而上

 1 #include <iostream>
 2 using namespace std;
 3 
 4 static int maze[100][100];//存储到达每一个房间收集到的最多券
 5 static int data[100][100];//存储每一个房间的券
 6 
 7 int main()
 8 {
 9     int maxLevel, i = 0, max = 0;
10     cin >> maxLevel;
11     
12     for (i = 0; i < maxLevel; i++)
13         for (int j = 0; j <= i; j++)
14             cin >> data[i][j];
15     //由低层到高层计算
16     maze[0][0] = data[0][0];
17     for (int i = 1; i < maxLevel; i++)
18     {
19         for (int j = 0; j <= i; j++)
20         {
21             if (j > 0 && maze[i - 1][j] < maze[i - 1][j - 1])
22                 maze[i][j] = maze[i - 1][j - 1];
23             else
24                 maze[i][j] = maze[i - 1][j];
25             maze[i][j] += data[i][j];
26         }
27     }
28     //找出最后一层中券最多的房间
29     for (i = 0; i < maxLevel; i++)
30     {
31         int tmp = maxLevel - 1;
32         if (max < maze[tmp][i])
33             max = maze[tmp][i];
34     }
35     cout << max << endl;
36     return 0;
37 }

View Code

递归方式，从上而下

 1 #include <iostream>
 2 using namespace std;
 3 
 4 int maze[100][100];
 5 int data[100][100];
 6 void dp(int level)
 7 {
 8     if (level < 0)
 9         return;
10     dp(level - 1);
11     for (int room = 0; room <= level; room++)
12     {
13         if (level > 0)
14         {
15             if (room > 0)
16                 maze[level][room] = maze[level - 1][room] > maze[level - 1][room - 1] ? maze[level - 1][room] : maze[level - 1][room - 1];
17             else
18                 maze[level][room] = maze[level - 1][room];
19         }
20         else
21             maze[level][room] = 0;
22         maze[level][room] += data[level][room];
23     }
24 }
25 int main()
26 {
27     int maxLevel, i = 0, max = 0;
28     cin >> maxLevel;
29     
30     for (i = 0; i < maxLevel; i++)
31         for (int j = 0; j <= i; j++)
32             cin >> data[i][j];
33     dp(maxLevel - 1);
34     for (i = 0; i < maxLevel; i++)
35     {
36         int tmp = maxLevel - 1;
37         if (max < maze[tmp][i])
38             max = maze[tmp][i];
39     }
40     cout << max << endl;
41     return 0;
42 }

View Code