程序填空题：求解三角形最小路径问题（动态规划法）

给定高度为n的一个整数三角形，找出从顶部到底部的最小路径和，只能向左下右下移动到相邻的结点。

```c++
#include 
#include  
#include 
using namespace std;
#define MAXN 100
//问题表示
int a[MAXN][MAXN];
int n;
//求解结果表示
int ans=0;
int dp[MAXN][MAXN];
int pre[MAXN][MAXN];
int Search()						//求最小和路径ans
{	int i,j;
	dp[0][0]=a[0][0];
	for(i=1;idp[n-1][j])
		{	;
			k=j;
		}
	}
	return k;
}

void Disppath1(int k)					//输出最小和路径
{	int i=n-1;
	stack path;					//存放逆路径向量path
	while (i>=0)					//从（n-1,k）结点反推求出反向路径
	{	path.push(a[i][k]);
		;	
		i--;						//在前一行查找
	}
	while(!path.empty())
		{printf("%d ",path.top());	path.pop();}		//反向输出构成正向路径
}

int main()
{	int k;
	memset(pre,0,sizeof(pre));
	memset(dp,0,sizeof(dp));
	scanf("%d",&n);				//输入三角形的高度
	for (int i=0;i
答案：
第1空：dp[i-1][0]+a[i][0]    

第2空：0    

第3空：a[i][i]+dp[i-1][i-1]    

第4空：i-1    

第5空：j-1    

第6空：a[i][j]+dp[i-1][j-1]    

第7空：j    

第8空：a[i][j]+dp[i-1][j]    

第9空：ans=dp[n-1][j]    

第10空：k=pre[i][k]