原题链接:https://www.luogu.com.cn/problem/P1216
题意解读:计算数字三角形最高点到最后一行路径之和最大值,典型线性DP。
解题思路:
设a[i][j]表示数字三角形的值,
设dp[i][j]表示从最高点到第i行第j列路径之和的最大值,
由于每一步可以走到左下方的点也可以到达右下方的点,
所以dp[i][j] = dp[i][j] = max(dp[i-1][j], dp[i-1][j-1]) + a[i][j],
如果数组下标从1开始,且默认值为0,则不用考虑数组边界和初始化问题。
100分代码:
#include <bits/stdc++.h>
using namespace std;
const int N = 1005;
int r, a[N][N], dp[N][N];
int ans;
int main()
{
cin >> r;
for(int i = 1; i <= r; i++)
for(int j = 1; j <= i; j++)
cin >> a[i][j];
for(int i = 1; i <= r; i++)
for(int j = 1; j <= i; j++)
dp[i][j] = max(dp[i-1][j], dp[i-1][j-1]) + a[i][j];
for(int j = 1; j <= r; j++) ans = max(ans, dp[r][j]);
cout << ans;
return 0;
}
标签:数字,USACO1.5,int,洛谷题,Number,P1216,三角形,dp From: https://www.cnblogs.com/jcwy/p/18142820