[数据结构与算法]练习3，初见动态规划之经典的三角形问题[动态规划DP]

zhuang'tai'zhuan'yi题目为[USACO1.5][IOI1994]数字三角形 Number Triangles

状态转移方程为：d(i,j)=a(i,j)+max[d(i+1,j),d(i+1,j+1)]

思路源于《算法竞赛入门经典》

#include<bits/stdc++.h>
using namespace std;
int a[1000][1000],r,d[1000][1000];
int so(int i, int j){
    if(d[i][j]>=0) return d[i][j];
    return d[i][j]=a[i][j]+(i == r ? 0 : max(so(i+1,j),so(i+1,j+1)));
}
int main(){
    cin >> r;
    for(int i=1;i<=r;i++)
        for(int j=1;j<=i;j++) cin >> a[i][j];
        memset(d,-1,sizeof(d));
    cout <<so(1,1);
    return 0;
}