传送门http://acm.sdut.edu.cn/sdutoj/problem.php?action=showproblem&problemid=1730
小白动态规划里的例题.
从后往上递推计算.
#include <cstdio>
#include <algorithm>
using namespace std;
int n;
int a[110][110];
int main()
{
int d[110][110];
//freopen("input.txt", "r", stdin);
int i, j;
scanf("%d", &n);
for (i = 1; i <= n; i++)
for (j = 1; j <= i; j++)
scanf("%d", &a[i][j]);
for (j = 1; j <= i; j++)
d[n][j] = a[n][j];
for (i = n - 1; i >= 1; i--)
for (j = 1; j <= i; j++)
if (d[i + 1][j] > d[i + 1][j + 1])
d[i][j] = a[i][j] + d[i + 1][j];
else
d[i][j] = a[i][j] + d[i + 1][j + 1];
printf("%d\n",d[1][1]);
return 0;
}