PKU 1163 The Triangle

• 動的計画法
• 直前のマスの最適解を用いて現在のマスの最適解を求める

int main() {
	int N;
	cin >> N;

	int first;
	cin >> first;

	vector<int> dp;
	dp.push_back(first);

	int bestAnswer = INT_MIN;
	for (int n = 2; n <= N; ++n) {
		vector<int> next;
		for (int i = 0; i < n; ++i) {
			int value;
			cin >> value;
			int sum = INT_MIN;

			if (i) {
				sum = max(sum, value + dp[i - 1]);
			}

			if (i < n - 1) {
				sum = max(sum, value + dp[i]);
			}

			next.push_back(sum);

			bestAnswer = max(bestAnswer, sum);
		}

		swap(dp, next);
	}

	cout << bestAnswer << endl;
}