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
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/598986.html