程序填空题：求解三角形最小路径问题（动态规划法）
给定高度为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;i { dp[i][0]=;
pre[i][0]=;
}
for (i=1;i { dp[i][i]=;
pre[i][i]=;
}
for(i=2;i { for(j=1;j { if(dp[i-1][j-1] { pre[i][j]=;
dp[i][j]=;
}
else
{ pre[i][j]=;
dp[i][j]=;
}
}
}
ans=dp[n-1][0];
int k=0;
for (j=1;j { if (ans>dp[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 for (int j=0;j<=i;j++)
scanf("%d",&a[i][j]);
k=Search(); //求最小路径和
Disppath1(k); //输出正向路径
printf("\n%d",ans); //输出最小路径和
return 0;
}
```
### 输入格式:
首先输入n，接下来的1～n行，第i行输入i个整数。
### 输出格式:
输出第一行为最小路径，第2行为最小路径和。
### 输入样例1:
```in
4
2
3 4
6 5 7
8 3 9 2
```
### 输出样例1:
```out
2 3 5 3
13
```
答案：
第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]
```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;i
pre[i][0]=;
}
for (i=1;i
pre[i][i]=;
}
for(i=2;i
dp[i][j]=;
}
else
{ pre[i][j]=;
dp[i][j]=;
}
}
}
ans=dp[n-1][0];
int k=0;
for (j=1;j
{ ;
k=j;
}
}
return k;
}
void Disppath1(int k) //输出最小和路径
{ int i=n-1;
stack
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
scanf("%d",&a[i][j]);
k=Search(); //求最小路径和
Disppath1(k); //输出正向路径
printf("\n%d",ans); //输出最小路径和
return 0;
}
```
### 输入格式:
首先输入n，接下来的1～n行，第i行输入i个整数。
### 输出格式:
输出第一行为最小路径，第2行为最小路径和。
### 输入样例1:
```in
4
2
3 4
6 5 7
8 3 9 2
```
### 输出样例1:
```out
2 3 5 3
13
```
答案：
第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]
