[蓝桥杯]算法训练-数字三角形

  • 内容
  • 评论
  • 相关

题目描述
[解题思路]
一开始看到这题,我想到的思路是从上向下遍历,然后将每个结果都存储起来,然而按照这个思路实现了一下,发现代码太长了,而且不能完全AC。然后就想到了是不是用动态规划求解,也想了一些思路,但是奈何水平不够,实现不了。于是就求助人类的希望Google(大雾),找到了一种特别简单而且高效的思路,用记忆化搜索。从下向遍历三角形,并且每次都将此次运算的结果储存起来,生成一个新的三角形,直到只剩一个元素,即为要求的最大值了。
[代码]

#include 
 
using namespace std;

int main() 
{
int n;
cin >> n;
int a[n + 1][n + 1];
for(int i = 1; i <= n; i++)
for(int j = 1; j <= i; j++)
cin >> a[i][j];
for(int i = n - 1; i >= 0; i--)
for(int j = 1; j <= i; j++)
if(a[i+1][j+1] > a[i+1][j])
a[i][j] += a[i+1][j+1];
else
a[i][j] += a[i+1][j];
cout << a[1][1];
return 0;
}