给定一个正三角形数组,自顶到底分别有 1,2,3,4,5...,n 个元素,找出自顶向下的最小路径和。
每一步只能移动到下一行的相邻节点上,相邻节点指下行种下标与之相同或下标加一的两个节点。
数据范围:三角形数组行数满足 ,数组中的值都满足
例如当输入[[2],[3,4],[6,5,7],[4,1,8,3]]时,对应的输出为11,
所选的路径如下图所示:
[[10]]
10
[[2],[3,4],[6,5,7],[4,1,8,3]]
11
最小路径是 2 , 3 ,5 , 1
[[1],[-1000,0]]
-999
int minTrace(vector<vector<int> >& triangle) { int n = triangle.size(); for (int i = 1; i < n; ++i) { for (int j = 0; j < triangle[i].size(); ++j) { if (j == 0) triangle[i][j] += triangle[i - 1][j]; else if (j == triangle[i].size() - 1) triangle[i][j] += triangle[i - 1][j - 1]; else { triangle[i][j] += min(triangle[i - 1][j - 1], triangle[i - 1][j]); } } } int res = triangle[n - 1][0]; for (int i = 0; i < triangle[n - 1].size(); ++i) { res = min(res, triangle[n - 1][i]); } }
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param triangle int整型二维数组 * @return int整型 */ public int minTrace (int[][] triangle) { // write code here int n = triangle.length; for(int i = n - 2; i >= 0; i--){ int m = triangle[i].length; for(int j = 0; j < m; j++){ triangle[i][j] += Math.min(triangle[i + 1][j], triangle[i + 1][j + 1]); } } return triangle[0][0]; } }
int minTrace(vector<vector<int> >& triangle) { // write code here int n = triangle.size(); vector<vector<int> > dp(n, vector<int>(n)); dp[0][0] = triangle[0][0]; for (int i = 1; i < n; ++i) { for (int j = 0; j < triangle[i].size(); ++j) { if (j == 0) { dp[i][0] = dp[i - 1][0] + triangle[i][0]; } else if (j == i) { dp[i][i] = dp[i - 1][i - 1] + triangle[i][i]; } else { dp[i][j] = triangle[i][j] + min(dp[i - 1][j], dp[i - 1][j - 1]); } } } int res = dp[n - 1][0]; for (int i = 1; i < n; ++i) { res = min(res, dp[n - 1][i]); } return res; }
#include <climits> class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param triangle int整型vector<vector<>> * @return int整型 */ int minTrace(vector<vector<int> >& triangle) { // write code here int n = triangle.size(); vector<int> dp(n, INT_MAX); dp[0] = triangle[0][0]; for(int i=1; i<n; i++){ for(int j=i; j>0; j--){ dp[j] = min(dp[j],dp[j-1])+triangle[i][j]; } dp[0] = dp[0]+triangle[i][0]; } int res = INT_MAX; for(int v : dp){ if(v<res) res = v; } return res; } };
#include <climits> class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param triangle int整型vector<vector<>> * @return int整型 */ int minTrace(vector<vector<int> >& triangle) { int m = triangle.size(); vector<vector<int>> dp(m + 1, vector<int>(m + 1, INT_MAX)); dp[0][0] = dp[0][1] = 0; for (int i = 1; i <= m; i++) { for (int j = 1; j <= i; j++) { dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - 1]) + triangle[i - 1][j - 1]; } } int ret = INT_MAX; for (int i = 1; i <= m; i++) { ret = min(ret, dp[m][i]); } return ret; } };
#include <algorithm> class Solution { public: int minTrace(vector<vector<int> >& triangle) { vector<vector<int>> minPathSum(triangle); int row=triangle.size(); //从最后一行开始向上推导 for(int i=row-2;i>=0;--i) { for(int j=0;j<=i;++j) { minPathSum[i][j]=min(minPathSum[i+1][j+1],minPathSum[i+1][j])+triangle[i][j]; } } return minPathSum[0][0]; } };
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param triangle int整型二维数组 * @return int整型 */ public int minTrace (int[][] triangle) { // write code here //当处于triangle[i][j]位置时候,到达该位置的最小路径和为dp[i][j]; int dp[][]=new int[triangle.length][triangle.length]; //初始化dp数组 dp[0][0]=triangle[0][0]; for(int i=1;i<triangle.length;i++){ for(int j=0;j<triangle[i].length;j++){ //当处于该行最左边 if(j==0){ dp[i][j]=dp[i-1][j]+triangle[i][j]; //当处于该行最右边 }else if(i==j){ dp[i][j]=dp[i-1][j-1]+triangle[i][j]; //当处于该行中间 }else{ dp[i][j]=Math.min(dp[i-1][j]+triangle[i][j],dp[i-1][j-1]+triangle[i][j]); } } } //寻找最后一行最大值 int min=Integer.MAX_VALUE; for(int i=0;i<triangle.length;i++){ if(dp[triangle.length-1][i]<min){ min=dp[triangle.length-1][i]; } } return min; } }
class Solution: def minTrace(self , triangle: List[List[int]]) -> int: # 定义dp[i][j]为从下往上到第[i,j]个元素时的最小路径和 # 最后结果为dp[0][0] # dp转移方程为: dp[i][j] = min(dp[i+1][j], dp[i+1][j+1]) + triangle[i][j] # 初始状态: dp[m-1][j] = triangle[m-1][j] m, n = len(triangle), len(triangle[-1]) dp = [[0 for _ in range(n)] for _ in range(m)] for j in range(n): dp[m-1][j] = triangle[m-1][j] for i in range(m-2, -1, -1): for j in range(i+1): dp[i][j] = min(dp[i+1][j], dp[i+1][j+1]) + triangle[i][j] return dp[0][0]
using System; using System.Collections.Generic; class Solution { public int minTrace(List<List<int>> triangle) { // f[y][x]表示到点(x, y)的最短路径长度 // f[y][x] = triangle[y][x] + min(f[y - 1][x - 1]+ f[y - 1][x]) List<List<int>> dp = triangle; for (int y = 1; y < dp.Count; ++y) { dp[y][0] += dp[y - 1][0]; for (int x = 1; x < dp[y].Count - 1; ++x) dp[y][x] += Math.Min(dp[y - 1][x - 1], dp[y - 1][x]); dp[y][dp[y].Count - 1] += dp[y - 1][dp[y].Count - 2]; } int minDist = dp[dp.Count - 1][0]; for (int x = 1; x < dp[dp.Count - 1].Count; ++x) minDist = Math.Min(minDist, dp[dp.Count - 1][x]); return minDist; } }
/** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param triangle int整型二维数组 * @return int整型 */ function minTrace( triangle ) { let m=triangle.length; for(let i=1;i<m;i++){ triangle[i][0]+=triangle[i-1][0]; triangle[i][triangle[i].length-1]+=triangle[i-1][triangle[i-1].length-1]; } for(let i=2;i<m;i++){ for(let j=1;j<triangle[i].length-1;j++){ triangle[i][j]+=Math.min(triangle[i-1][j-1],triangle[i-1][j]); } } return triangle[m-1].reduce((pre,cur)=>Math.min(pre,cur)); } module.exports = { minTrace : minTrace };
import java.util.*; public class Solution { /** * 自底向上 * @param triangle int整型二维数组 * @return int整型 */ public int minTrace (int[][] triangle) { int n=triangle.length; for(int i=n-2;i>=0;i--){//倒数第二层 for(int j=0;j<triangle[i].length;j++){//倒数第一层 //倒数第二层的每个值,都依赖下一层相同下标j 和 相邻下标j+1 的值,取最小即可 triangle[i][j]+=Math.min(triangle[i+1][j],triangle[i+1][j+1]); } } return triangle[0][0]; } }
class Solution: def minTrace(self , triangle: List[List[int]]) -> int: dp_lst = [0] for i in triangle: dp_lst2 = dp_lst.copy() dp_lst = [100000] for j in range(len(i)): dp_lst.append(min(dp_lst2[j: j + 3]) + i[j]) return min(dp_lst[1:])我只能说应该是最后两个用例出问题了,已经检查出-63结果应该是-69。
大佬能帮我看看这哪出bug了,就测试用例通过66%, [[-7], [-2,1], [-5,-5,9], [-4,-5,4,4], [-6,-6,2,-1,-5], [3,7,8,-3,7,-9], [-9,-1,-9,6,9,0,7], [-7,0,-6,-8,7,1,-4,9], [-3,2,-6,-9,-7,-6,-9,4,0], [-8,-6,-3,-9,-2,-6,7,-5,0,7], [-9,-1,-2,4,-2,4,4,-1,2,-5,5], [1,1,-6,1,-2,-4,4,-2,6,-6,0,6], [-3,-3,-6,-2,-6,-2,7,-9,-5,-7,-5,5,1]] 上面用例报错,一个是-63,一个是-61 import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 *行数为:"+arr.length *列数为":+arr[0].length * @param triangle int整型二维数组 * @return int整型 */ public int minTrace (int[][] triangle) { // write code here //动态规划 //定义数组,存放结果,即三角形最短路径和 int n=triangle.length; int[] dp=new int[n]; //初值 dp[0]=triangle[0][0];//0行0列 if(n==1){ return dp[0]; }else{ int j=0;//列值 for(int i=1;i<=n;i++){ dp[i]=dp[i-1]+min(triangle[i][j],triangle[i][j+1]);//动态规划 //更新列值 if(triangle[i][j]>triangle[i][j+1]){ j++; } } return dp[n-1]; } } //定义比较大小函数 private int min(int i,int j){ if(i<=j) return i; else{ return j; } } }