数字三角形
题目
给定一个如下图所示的 n n n层数字三角形，从顶部出发，在每一结点可以选择移动至其左下方的结点或移动至其右下方的结点，一直走到底层，要求找出一条路径，使路径上的数字的和最大。
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
题解
正序
以
f
[
x
]
[
y
]
f[x][y]
f[x][y]表示其为在第
x
x
x行，第
y
y
y个与之前数字之和最大的数，则：
f
[
x
]
[
y
]
=
a
[
x
]
[
y
]
+
m
a
x
(
f
[
x
−
1
]
[
y
−
1
]
,
f
[
x
−
1
]
[
y
]
)
f[x][y]=a[x][y]+max(f[x-1][y-1] ,f[x-1][y])
f[x][y]=a[x][y]+max(f[x−1][y−1],f[x−1][y])
决策过程中，我们仅需判断一下边界情况即可，即：
- 最左侧： f [ x ] [ y ] = a [ x ] [ y ] + f [ x − 1 ] [ y ] f[x][y]=a[x][y]+f[x-1][y] f[x][y]=a[x][y]+f[x−1][y].
- 最右侧： f [ x ] [ y ] = a [ x ] [ y ] + f [ x − 1 ] [ y − 1 ] f[x][y]=a[x][y]+f[x-1][y-1] f[x][y]=a[x][y]+f[x−1][y−1].
最终可以得到数组 f [ n ] [ y ] f[n][y] f[n][y]，只需比较出其中的最大值即可：
#include<iostream>
using namespace std;
int n, f[1005][1005], a[1005][1005] ,inf = 1e9;
int main()
{
cin >> n;
for(int i = 1 ;i <= n ;i ++)
for(int j = 1 ;j <= i ;j ++)
cin >> a[i][j];
f[1][1] = a[1][1];
for(int i = 2 ;i <= n ;i ++)
for(int j = 1 ;j <= i ;j ++)
{
if(j == i) f[i][j] = a[i][j] + f[i - 1][j - 1];
else if(j == 1) f[i][j] = a[i][j] + f[i - 1][j];
else f[i][j] = a[i][j] + max(f[i - 1][j - 1] , f[i - 1][j]);
}
int ans = -inf;
for(int i = 1 ;i <= n ;i ++)
ans = max(ans ,f[n][i]);
cout << ans << endl;
return 0;
}
也可将边界的数组设为无穷大负数，如果加入该数则必定为最小数来避免边界条件的分析：
#include<iostream>
#include<cmath>
using namespace std;
int n, f[1005][1005], a[1005][1005] ,inf = 1e9;
int main()
{
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 + 1 ;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] = a[i][j] + max(f[i - 1][j - 1] , f[i - 1][j]);
int ans = -inf;
for(int i = 1 ;i <= n ;i ++)
ans = max(ans ,f[n][i]);
cout << ans << endl;
return 0;
}
当然，这个也可以将其转化为一维数组求解 f [ y ] f[y] f[y]直接表示 f [ n ] [ y ] f[n][y] f[n][y]，不过变成了一层一层的枚举罢了：
#include<iostream>
#include<cmath>
using namespace std;
int n, f[1005], a[1005], inf = 1e9;
int main()
{
cin >> n;
for(int i = 0 ;i <= n + 1 ;i ++)
f[i] = -inf;
cin >> f[1];
for(int i = 2 ;i <= n; i ++)
{
for(int j = 1 ;j <= i ;j ++)
cin >> a[j];
for(int j = i ;j >= 1 ;j --)
f[j] = a[j] + max(f[j - 1] ,f[j]);
}
int ans = -inf;
for(int i = 1 ;i <= n ;i ++)
ans = max(ans , f[i]);
cout << ans << endl;
return 0;
}
同背包问题中，逆序防止数据被污染f[j] = max(f[j - 1] , f[j]) + a[j].
逆序
将三角形倒置后（数据输入仍是正序输入的，不过可以逆序规划）：
4 5 2 6 5
2 7 4 4
8 1 0
3 8
7
则方程变为了：
f
[
i
]
[
j
]
=
m
a
x
(
f
[
i
+
1
]
[
j
]
,
f
[
i
+
1
]
[
j
+
1
]
)
+
a
[
i
]
[
j
]
f[i][j]=max(f[i + 1][j],f[i+1][j+1])+a[i][j]
f[i][j]=max(f[i+1][j],f[i+1][j+1])+a[i][j]
#include<iostream>
#include<cmath>
using namespace std;
int n, f[1005], a[1005][1005];
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 = n ;i >= 1 ; i--)
for(int j = 1 ;j <= n ; j++)
f[j] = max(f[j] , f[j + 1]) + a[i][j];
cout << f[1];
return 0;
}