给定一个正三角形数组,自顶到底分别有 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
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; } }
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]; } }
大佬能帮我看看这哪出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; } } }
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]; } }