AcWing 898. 数字三角形
原题链接
简单
作者:
pw0rld
,
2021-01-15 20:26:28
,
所有人可见
,
阅读 278
自己的题解,看各位大佬题解,自己写了一个
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int n;
int w[510][510],f[510][510]; //定义两个数组
// //从下网上
// int main()
// {
// cin >> n;
// for(int i=1;i <= n;i++)
// for(int j=1;j<=i;j++)
// cin >> w[i][j]; //将数输入进去w数组
// for(int i=1;i<=n;i++) f[n][i] = w[n][i];
// for(int i=n-1;i;i--)
// for(int j=1;j<=i;j++)
// f[i][j] = max(f[i+1][j]+w[i][j],f[i+1][j+1]+w[i][j]);
// cout << f[1][1] << endl;
// return 0;
// }
//从上往下
int main()
{
memset(f,-0x3f3f3f3f, sizeof f);//把f初始化为最小的,因为考虑到输入的可能是负数字
cin >> n;
for(int i=1;i<=n;i++) //为什么从1开始,就是留了一个0的哨兵
for(int j=1;j<=i;j++)
cin >> w[i][j];
f[1][1] = w[1][1];//第一个为w[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]) + w[i][j]; //朝左或者朝右走,看看哪个加起来大。
}
}
int res = -0x3f3f3f3f;
for(int j = 0; j <= n; j ++) res = max(res, f[n][j]);//遍历最后一层
cout << res << endl;
return 0;
}
/*
n=5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
*/ //从上往下开始会生成这样一个矩阵 举例子
/*
0 7 0 0 0 0
10 15 0 0 0 0
18 16 15 0 0 0
20 25 23 19 19 0
24 30 27 29 24 0
*/
https://www.acwing.com/solution/content/17544/