View Code of Problem 4063

#include<iostream>
#include<cstdio>
#include<string>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<cctype>
using namespace std;
/*利用状态转移方程
dp[i][j]=max(dp[i+1][j],dp[i+1][j+1])+f[i][j];
*/ 
int main()
{
	int n,i,j,k;
	while( cin>>n && n!=0 ){
		int f[n+1][n+1],dp[n+1][n+1];
		for( i=1;i<=n;i++ ){
			for( j=1;j<=i;j++ )
			cin>>f[i][j]; 
		}
		for( i=1;i<=n;i++ ){
			dp[n][i]=f[n][i];
		}//初始dp数组构造完毕
		for( i=n-1;i>0;i-- ){
		 	for( j=1;j<=i;j++ ){
		 		dp[i][j] = min( dp[i+1][j],dp[i+1][j+1] ) + f[i][j];
			}
		}
		cout<<dp[1][1]<<endl;
	}
}