目录
显示
题目链接
https://www.luogu.org/problem/P1216
http://poj.org/problem?id=1163
题解
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; }