欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

120. 三角形最小路径和 (C语言+暴力递归+优化递归+动态规划+空间优化动态规划)

程序员文章站 2022-04-17 08:38:42
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 triangleSiz...

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


120. 三角形最小路径和  (C语言+暴力递归+优化递归+动态规划+空间优化动态规划)
120. 三角形最小路径和  (C语言+暴力递归+优化递归+动态规划+空间优化动态规划)

本文地址:https://blog.csdn.net/sumisu666/article/details/107334826