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];
}