题目描述 给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。
例如，给定三角形
代码语言：javascript复制[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]自顶向下的最小路径和为 11（即，2 3 5 1 = 11）。
说明：
如果你可以只使用 O(n) 的额外空间（n 为三角形的总行数）来解决这个问题，那么你的算法会很加分。
分析：从题目中看出，第n行三角形中有n个数字。可以用一个二维数组存储数字三角形。需要找出自顶向下的最小路径和，则需要找到每一行的最小值。 用dp[1][1]表示最小路径和。 要找前两行的最小路径和,则需要找到与（1，1）下一行相邻的两个点（2，1）到底的最小路劲和（2，2），决策出最小的路径和，dp[1][1] = min(dp[2][1]，dp[2][2]) f[1][1]; 对于dp[i][j]，则其求解为: dp[i][j] = min{dp[i 1][j],dp[i 1][j 1]} f[i][j]。 即为状态转移方程，将dp[i][j]称为状态。 边界条件：对于最后一行，最小路径和即为元素自身的值。 AC代码：
代码语言：javascript复制#include <cstdio>
#include <cassert>
#include <cstring>
#include <algorithm>
const int maxn = 1000;
int f[maxn][maxn];
int dp[maxn][maxn];
int main(){
int n;
scanf("%d",&n);
for(int i=1;i <= n; i){
for(int j=1;j <= i; j){
scanf("%d",&f[i][j]);
}
}
for(int j=1;j <= n; j){
dp[n][j] = f[n][j];
}
for(int i=n-1;i >= 1;--i){
for(int j=1;j <= i; j){
dp[i][j] = f[i][j] std::min(dp[i 1][j],dp[i 1][j 1]);
}
}
printf("%dn",dp[1][1]);
for(int i=1;i<=n; i){
for(int j=1;j <= i; j){
printf("dp[%d][%d]=%d ",i,j,dp[i][j]);
}
printf("n");
}
}执行结果：
