POJ 1163

数字塔，非常舒服的DP，自底向上的递归搜索填表，非常归整

#include <iostream>
#include <algorithm>
#include <queue>
#include <string>
#include <vector>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <string>
#include <stack>
#include <map>
#include <set>
using namespace std;

const int maxn= 105;

int tow[maxn][maxn];
int dv[maxn][maxn];

int main(int argc, char const *argv[])
{
	int n;
	scanf("%d", &n);
	for (int i= 1; i<= n; ++i){
		for (int j= 1; j<= i; ++j){
			scanf("%d", tow[i]+j);
		}
	}
	memset(dv, -1, sizeof(dv));

	dv[0][1]= 0;
	for (int i= 1; i<= n; ++i){
		dv[i][1]= dv[i-1][1]+tow[i][1];
	}

	for (int i= 2; i<= n; ++i){
		dv[i][i]= dv[i-1][i-1]+tow[i][i];
	}

	for (int i= 3; i<= n; ++i){
		for (int j= 2; j< i; ++j){
			dv[i][j]= max(dv[i-1][j-1], dv[i-1][j])+tow[i][j];
		}
	}

	int ans= -1;
	for (int i= 1; i<= n; ++i){
		ans= max(ans, dv[n][i]);
	}

	printf("%d
", ans);
	return 0;
}