题解

首先，数据范围给错了，n必须在10000以下，不然光是存储数组就会RE
其次，我们必须从下往上来算，这样才能有状态转移方程：
$dp[i][j] = min(dp[i + 1][j], dp[i + 1][j + 1], dp[i + 1][j + 2]) + a[i][j]$
因为每个都由左中右三个点过来
知道状态转移方程以后，事情就变得简单了：

#include <iostream>
#include <cstdio>
using namespace std;
int a[1005][1005], dp[1005][1005];
int read(){
	char c = getchar();
	int x = 0, f = 1;
	while(!isdigit(c)){
		if(c == '-') f = -f;
		c = getchar(); 
	}while(isdigit(c)){
		x = x * 10 + c - '0';
		c = getchar();
	}return x * f;
}
int main(){
	int n = read();
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= i * 2 - 1; j++){
			a[i][j] = read();
		}
	}for(int i = n; i >= 1; i--){//从下往上走
		for(int j = 1; j <= i * 2 - 1; j++){
			dp[i][j] = min(dp[i + 1][j], min(dp[i + 1][j + 1], dp[i + 1][j + 2])) + a[i][j];//状态转移方程
		}
	}cout << dp[1][1];

	return 0;
}

时间复杂度：$O(n^2)$