View Code of Problem 65

#include<bits/stdc++.h>
using namespace std;
int main() {
	int len;
	cin >> len;
	while (len--) {
		int w=0;
		cin >> w;
		//存入数组
		vector<vector<int>> v(w + 1, vector<int>(w + 1));
		for (int i = 1; i <= w; i++) {
			for (int j = 1; j <= i; j++) {
				cin >> v[i][j];
			}
		}
		//初始化值:复制v最后一行到dp中
		vector<vector<int>> dp(w + 1, vector<int>(w + 1));
		for (int i = 1; i <= w; i++) {
			dp[w][i] = v[w][i];
		}
 
		//开始动态规划
		for (int i = w - 1; i >= 1; i--) {
			for (int j = 1; j <= i; j++) {
				dp[i][j] = max(dp[i + 1][j], dp[i + 1][j + 1]) + v[i][j];
			}
		}
		cout << dp[1][1]<<endl;
	}
	return 0;
}