一:题目

在这里插入图片描述

二:代码

#include <iostream>
#include<vector>
using namespace std;
int main()
{
  /**
	思路:
		1.确定dp数组的定义以及下标的含义
			dp[i][j] 表示的是一条路径到达下标i和j时，的最大值 
		2.确定dp数组的状态转移公式
			
			我们当前位置的最大值其实是由右上方和左上方中最大的值决定的（题目给出的第一个图） 
			
			dp[i][j] = max(dp[i-1][j-1],dp[i-1][j]) + v[i][j]; 
			 
		3.确定dp数组的初始化
			dp数组初始化为0 
		
		4.确定dp数组的遍历顺序
			正常遍历即可，但是我们需要将我们原始数组中 最上面的一行 和 最左面的一行空出来 
			因为当 i = 1 j = 1时 我们需要 dp[0][j] 和 dp[i][0] 
			
		5.举例验证 
		
		
		
		
*/ 

	
	int n;
	int ans = 0;
	
	cin >> n;
	
	vector<vector<int> >v1(n+1,vector<int>(n+1,0)); 
	vector<vector<int> >dp(n+1,vector<int>(n+1,0)); 
	
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= i; j++) {
			cin >> v1[i][j];
		}	
	}
	
	
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= i; j++) { 
			dp[i][j] = max(dp[i-1][j-1],dp[i-1][j]) + v1[i][j];
			if(ans < dp[i][j]) ans = dp[i][j];
		}	
	}
	
	//关于题目中说的 最终左的次数与右的次数相差不能大于1
	//通过观察发现 
	
	if(n%2 != 0) {
		cout << dp[n][(n+1)/2];
	} else {
		
		int num1 = dp[n][(n+1)/2];
		int num2 = dp[n][(n+1)/2+1];
		
		cout << max(num1,num2);
	}			
			
			
		
	//验证输出 
//	for (int i = 0; i <= n; i++) {
//		for (int j = 0; j <= n; j++) {
//			cout << v1[i][j] << " ";
//		}	
//		cout << endl;
//	}
//	
//	cout << "++++++++++++++" << endl;
//	
//	for (int i = 0; i <= n; i++) {
//		for (int j = 0; j <= n; j++) {
//			cout << dp[i][j] << " ";
//		}	
//		cout << endl;
//	}

//6
//7
//3 8
//8 1 0
//2 7 4 4
//4 5 2 6 5
//6 7 8 9 10 11
	
	

  return 0;
}