[数据结构与算法]蓝桥杯2021年第十二届真题-数字三角形

题目

题目链接

题解

动态规划

重点是如何分析“向左下走的次数与向右下走的次数相差不能超过 1”。

这句话保证了从山顶走到山底，如果高度为奇数，则一定落在最中间的位置，如果高度为偶数，则一定落在中间的两个位置。

即假设高度为$N$，每一行、列从索引0开始。如果$N$为奇数，则最后一定是到达$(N?1,N/2)$；如果$N$为偶数，则最后一定是到达$(N?1,N/2?1)$或$(N?1,N/2)$。

因此，我们只需要自上向下动规，最后输出对应位置的值，或者两个位置中的最大值。

动态规划的状态定义与转移方程与最普通的数字三角形是一样的。

代码

#include<bits/stdc++.h>
using namespace std;

int a[110][110], dp[110][110], n;

int main()
{
	cin >> n;
	for (int i = 0;i < n;i ++) 
	for (int j = 0;j <= i;j ++)	
	cin >> a[i][j];
	
	dp[0][0] = a[0][0];
	for (int i = 1;i < n;i ++) 
	for (int j = 0;j <= i;j ++) 
		dp[i][j] = a[i][j] + max(dp[i-1][j], j>=1?dp[i-1][j-1]:0);
	
	if (n & 1) cout << dp[n-1][n/2] << endl;
	else cout << max (dp[n-1][n/2-1], dp[n-1][n/2]);

//	for (int i = 0;i < n;i ++, cout << endl) 
//	for (int j = 0;j <= i;j ++)	
//	cout << dp[i][j] << ' ';

	return 0;
}
/*
7
3 8
8 1 0 
2 7 4 4
4 5 2 6 5
*/