HDU-2084 数塔
代码
#include <iostream>
using namespace std;
int main() {
int C;
cin>>C;
for(int i=0; i<C; i++) {
int N;
cin>>N;
int a[N][N];
for(int j=0; j<N; j++) {
for(int k=0; k<=j; k++) {
cin>>a[j][k];
}
}
if(N>1) {
for(int j=N-2; j>=0; j--) {
for(int k=0; k<=j; k++) {
a[j][k] += max(a[j+1][k], a[j+1][k+1]);
}
}
}
cout<<a[0][0]<<endl;
}
return 0;
}
注解
1、dp的典型例题。
2、从下往上一层层计算。
3、特别注意N=1的情况。