簡(jiǎn)單的dp題
由于每次只用到tri[n-1]的信息，所以可以?xún)?yōu)化為空間復(fù)雜度為O(n)，但代碼要復(fù)雜得一些。keep it simple,:-)
#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("numtri.in");
ofstream fout("numtri.out");
#ifdef _DEBUG
#define out cout
#define in cin
#else
#define out fout
#define in fin
#endif
int tri[1000][1000];
void solve()
{
int r;
in>>r;
for(int i=0;i<r;++i){
for(int j=0;j<i+1;++j){
in>>tri[i][j];
}
}
//處理一下邊界
for(int i=1;i<r;++i){
tri[i][0]+=tri[i-1][0];
tri[i][i]+=tri[i-1][i-1];
}
for(int i=2;i<r;++i){
for(int j=1;j<i;++j){
tri[i][j]+=max(tri[i-1][j-1],tri[i-1][j]);
}
}
int res = INT_MIN;
for(int i=0;i<r;++i){
res = max(res,tri[r-1][i]);
}
out<<res<<endl;
}
int main(int argc,char *argv[])
{
solve();
return 0;
}