120. 三角形最小路径和

给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。

相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。

例如，给定三角形：

[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]
自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。

/*解法1：递归   (超时) int dfs(int **triangle,int i,int j,int triangleSize) {    if(i == triangleSize) return 0;     return fmin(dfs(triangle,i+1,j,triangleSize),dfs(triangle,i+1,j+1,triangleSize)) + triangle[i][j]; }  int minimumTotal(int** triangle, int triangleSize, int* triangleColSize){        return dfs(triangle,0,0,triangleSize); } */  /*解法2：递归优化---减少重复计算 int dfs(int **triangle,int i,int j,int triangleSize,int **memo) {    if(i == triangleSize) return 0;     if(memo[i][j] != 0) return memo[i][j];     return memo[i][j] = fmin(dfs(triangle,i+1,j,triangleSize,memo),dfs(triangle,i+1,j+1,triangleSize,memo)) + triangle[i][j]; }  int minimumTotal(int** triangle, int triangleSize, int* triangleColSize){    int **memo;  //定义一个数组记录 计算的路径值，避免一些重复计算    memo = (int **)malloc(sizeof(int *) * triangleSize);     for(int i = 0;i < triangleSize;i++) {      memo[i] = (int *)malloc(sizeof(int) * triangleSize);      memset( memo[i],0,sizeof(int) * triangleSize );    }       return dfs(triangle,0,0,triangleSize,memo); } */  /*解法3：动态规划   自底向上 int minimumTotal(int** triangle, int triangleSize, int* triangleColSize){    int dp[triangleSize+1][triangleSize+1];    for(int i = 0;i < triangleSize+1;i++) {        dp[triangleSize][i] = 0;    }    for(int i = triangleSize-1;i >= 0;i--)        for(int j = 0;j <= i;j++) {           dp[i][j] = triangle[i][j] + fmin(dp[i+1][j],dp[i+1][j+1]);        }   return dp[0][0]; } */  //解法4：动态规划--空间优化   自底向上 int minimumTotal(int** triangle, int triangleSize, int* triangleColSize){    int dp[triangleSize+1];    for(int i = 0;i < triangleSize+1;i++) {        dp[i] = 0;    }    for(int i = triangleSize-1;i >= 0;i--)        for(int j = 0;j <= i;j++) {           dp[j] = triangle[i][j] + fmin(dp[j],dp[j+1]);        }   return dp[0]; }   

c/c++开发分享120. 三角形最小路径和 （C语言+暴力递归+优化递归+动态规划+空间优化动态规划）地址：https://blog.csdn.net/sumisu666/article/details/107334826