动态规划——Number Triangles

动态规划——Number Triangles"/>

动态规划——Number Triangles

动态规划——Number Triangles

来源于洛谷P1216 [USACO1.5][IOI1994]数字三角形 Number Triangles

解题思路

考虑从最后开始一直往前搜索的思路

直接转换为一维数组，每个数的左右孩子是其下标+层数、下标+层数+1

代码实现

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
const int SIZE = 600001;
int res[SIZE];
int nums[SIZE];
int n;
int k=0;
void  solve()
{int i, j;for (i = n-1; i >= 1; i--){for (j = 1; j <= i; j++){int lchild, rchild;lchild = k + i;rchild = k + i + 1;res[k] = max(res[lchild]+nums[lchild], res[rchild]+nums[rchild]);k--;}}}
int main()
{scanf("%d", &n);for (int i = 1; i <= n; i++){for (int j = 1; j <= i; j++)scanf("%d", &nums[k++]);}k--;k -= n;memset(res, 0, sizeof(res));solve();printf("%d", res[0]+nums[0]);return 0;
}

注意

这里的数组范围需要开到600000才不会报错，另外如果用二维数组的话应该会简单一点