蓝桥杯2021年第十二届真题-数字三角形

题目

题目链接

题解

动态规划

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

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

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

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

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

代码

#include
using namespace std;

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

int main()
{
	cin >> n;
	for (int i = 0;i  a[i][j];
	
	dp[0][0] = a[0][0];
	for (int i = 1;i