题目来源： https://www.acwing.com/problem/content/900/
题目描述：
给定一个如下图所示的数字三角形，从顶部出发，在每一结点可以选择移动至其左下方的结点或移动至其右下方的结点，一直走到底层，要求找出一条路径，使路径上的数字的和最大
这道题非常注重边界条件，比如矩阵的初始化，利用维度的选择比较有技巧，还有把不规则的三角形放在一个矩阵中这个技巧比较重要。
所以在三角形中，左边是行i，右边是列j，所以构造成一个三角矩阵，然后再通过求集合的方式，求出状态转移方程。
这里的属性取max，然后又正数有负数，有0，所以初始化的时候都初始化为-INF，这里非常重要。
所以状态转移方程就是：
$f[i][j] = max(f[i - 1][j - 1], f[i - 1][j]) + a[i][j]$
伪代码:
1
2
3
4
5
6
7
8
|
for i <- 1 to n
for j <- 1 to i
f[i][j] = max(f[i - 1][j - 1], f[i - 1][j]) + a[i][j]
res = -inf
for i <- 1 to n
res = max(res, f[n][i]
|
C++实现：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
|
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 550, INF = 1e9;
int a[N][N], f[N][N] = {-INF};
int main() {
int n;
cin >> n;
for( int i = 1; i <= n; i++)
for( int j = 1; j <= i; j++)
cin >> a[i][j];
for (int i = 0; i <= n; i++)
for(int j = 0; j <= i + 1; j++)
f[i][j] = -INF;
f[1][1] = a[1][1];
for ( int i = 2; i <= n; i++)
for(int j = 1; j <= i; j++)
f[i][j] = max(f[i - 1][j - 1], f[i - 1][j]) + a[i][j];
int res = -INF;
for (int i = 1; i <= n; i++)
res = max(res, f[n][i]);
cout << res << endl;
return 0;
}
|
也可以使用逆推的方式，这种方式不用考虑边界条件， 所以状态方程就变成：
$f[i][j] = max(f[i + 1][j], f[i + 1][j + 1]) + a[i][j]$
伪代码：
1
2
3
4
5
| for i <- n - 1 to 1
for j <- 1 to i
f[i][j] = max(f[i + 1][j], f[i + 1][j + 1]) + a[i][j]
res = f[1][1]
|
C++逆推实现：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
|
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 550;
int a[N][N], f[N][N];
int main() {
int n;
cin >> n;
for( int i = 1; i <= n; i++)
for( int j = 1; j <= i; j++)
cin >> a[i][j];
for(int i = 1; i <= n; i++)
f[n][i] = a[n][i];
for (int i = n - 1; i >= 1; i--)
for( int j = 1; j <= i; j++)
f[i][j] = max(f[i + 1][j], f[i + 1][j + 1]) + a[i][j];
cout << f[1][1] << endl;
return 0;
}
|
应为f[i][j] 都是由f[i + 1]转移过来的，所以也可以使用一维表示, 使用滚动数组。二维改成一维并不会有特别大的提升。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
|
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 550;
int a[N][N], f[N];
int main() {
int n;
cin >> n;
for( int i = 1; i <= n; i++)
for( int j = 1; j <= i; j++)
cin >> a[i][j];
for(int i = 1; i <= n; i++)
f[i] = a[n][i];
for (int i = n - 1; i >= 1; i--)
for( int j = 1; j <= i; j++)
f[j] = max(f[j], f[j + 1]) + a[i][j];
cout << f[1] << endl;
return 0;
}
|