[洛谷 1216,poj 1163,codevs 1220][IOI1994]The Triangle

题目链接

https://www.luogu.org/problem/P1216

http://poj.org/problem?id=1163

http://codevs.cn/problem/1220

题解

DP 中最简单（也是最经典）的一道问题，每次因为只有两种决策（往下方走或者往右下方走），所以状态转移方程很容易可以得出：

$$f_{i,j}=\max(f_{i-1,j}+a_{i,j},f_{i-1,j-1}+a_{i,j})$$

时间复杂度为 \(O(n^2)\) 。

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
int n,a[205][205],f[205][205],maxn;
int main()
{
 scanf("%d",&n);
 for(int i=1;i<=n;i++)
  for(int j=1;j<=i;j++)
   scanf("%d",&a[i][j]);
 for(int i=1;i<=n;i++)
  for(int j=1;j<=i;j++)
   f[i][j]=max(f[i-1][j]+a[i][j],f[i-1][j-1]+a[i][j]);
 for(int i=1;i<=n;i++)
  maxn=max(f[n][i],maxn);
 printf("%d",maxn);
 return 0;
}