我相信不少人，第一反应 肯定是 DFS 吧，所以 在这里 把 DFS 和 DP 的代码 都奉上。当然 单纯的 DFS 是过不了的。会超时！

#include <iostream>
#include <algorithm>

using namespace std;

int maxSum = 0;
int sum = 0;
int arr[1005][1005];
bool vis[1005][1005];
int R;

int off[2][2] = { {1,0},{1,1} };
int dp[1005][1005];

void dfs11(int x,int y) {
	if (vis[x][y]) {
		return;
	}
	else {
		vis[x][y] = true;
		sum += arr[x][y];
	}
	if (x == R) {// 已经走到了 最底部
		if (maxSum < sum) {
			maxSum = sum;
		}
		return;
	}

	for (int i = 0; i < 2; ++i) {
		int tempX = x + off[i][0];
		int tempY = y + off[i][1];
		if (tempY > tempX) {
			continue;
			
		}
		dfs11(tempX, tempY);
		vis[tempX][tempY] = false;
		sum -= arr[tempX][tempY];
	}

}

int main(void) {
	
	cin >> R;
	for (int i = 1; i <= R; ++i) {
		for (int j = 1; j <= i; ++j) {
			cin >> arr[i][j];
		}
	}

	//dfs11(1, 1);// 从 第一行 第一列 开始 走
	//dp[i][j] = dp[i-1][j] 
	for (int i = 1; i <= R; ++i) {
		for (int j = 1; j <= i; ++j) {
			if (j == 0) {
				dp[i][j] = dp[i - 1][j] + arr[i][j];// 只有一种选择
			}
			else if (j == i) {
				dp[i][j] = dp[i - 1][j - 1] + arr[i][j]; // 只有一种选择
			}
			else {
				dp[i][j] = max(dp[i - 1][j - 1], dp[i-1][j]) + arr[i][j];
			}
		}
	}

	for (int i = 1; i <= R; ++i) {
		maxSum = max(maxSum, dp[R][i]);
	}


	cout << maxSum << endl;

	return 0;
}