数塔问题变种题。

数塔的升级版，（i，j）位置可以有（i+1，j）（i+1，j+1），（i+1，j+2）走过来，也就是取走到这三个位置的最小值

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

看了一圈ac的代码大多数都有问题，题目要求是1e5的数据，但是1000内就能过， 嗯。。。 只能说数据非常水，很明显得用滚动数组优化dp。

虽然是变种数塔问题，但是难度大了许多，关键在于如何计算哈

这题有点像dp中的DJ

#include<bits/stdc++.h> using namespace std; const int a=300; int n, e[a][a], dp[a][a]; int main(){ cin>>n; for(int i=1;i<=n;i++){ for(int j=1;j<=2i-1;j++) cin>>e[i][j]; } for(int i=n;i>=1;i--){ for(int j=1;j<=2i-1;j++) dp[i][j]=min(min(dp[i+1][j],dp[i+1][j+2]),dp[i+1][j+1])+e[i][j]; } cout << dp[1][1]; return 0; }