给出一个三角形，计算从三角形顶部到底部的最小路径和，每一步都可以移动到下面一行相邻的数字，
例如，给出的三角形如下：
[[20],[30,40],[60,50,70],[40,10,80,30]]最小的从顶部到底部的路径和是20 + 30 + 50 + 10 = 110。
[编程题]三角形
/**
* 方法：动态规划
* 状态：
* 子状态：从(0,0)到(1,0),(1,1),(2,0),...(n,n)的最短路径和
* F(i,j): 从(0,0)到(i,j)的最短路径和
* 状态递推：
* F(i,j) = min( F(i-1, j-1), F(i-1, j)) + triangle[i][j]
* 初始值：
* F(0,0) = triangle[0][0]
* 返回结果：
* min(F(n-1, i))
* 最后一行最小的元素
*/
public class Solution {
public int minimumTotal(ArrayList<ArrayList<Integer>> triangle) {
if (triangle == null) return 0;
ArrayList<ArrayList<Integer>> result = new ArrayList<>();
int row = triangle.size();
for (int i = 0; i < row; i++) {
result.add(new ArrayList<>());
}
// F[0][0]初始化
result.get(0).add(triangle.get(0).get(0));
for (int i = 1; i < row; i++) {
//上一行的最小值
int curSum = 0;
for (int j = 0; j < triangle.get(i).size(); j++) {
// 处理左边界和右边界
if (j == 0) {
curSum = result.get(i - 1).get(0);
} else if (j == i) {
curSum = result.get(i - 1).get(j - 1);
} else {
curSum = Math.min(result.get(i - 1).get(j - 1), result.get(i - 1).get(j));
}
// F(i,j) = min( F(i-1, j-1), F(i-1, j)) + triangle[i][j]
result.get(i).add(curSum + triangle.get(i).get(j));
}
}
int size = triangle.size();
// min(F(n-1, i))
int allMin = result.get(size - 1).get(0);
//在最后一行找最小的值
for (int i = 1; i < result.get(size - 1).size(); i++) {
allMin = Math.min(result.get(size - 1).get(i), allMin);
}
return allMin;
}
}
编辑于 2020-08-01 00:26:27
回复(0)
import java.util.ArrayList;
public class Solution {
public int minimumTotal(ArrayList<ArrayList<Integer>> triangle) {
if(triangle.size()==0)
return 0;
if(triangle.size()==1)
return triangle.get(0).get(0);
int[] dp=new int[triangle.size()+1];
for(int i=triangle.size()-1;i>=0;i--){
ArrayList<Integer> cur=triangle.get(i);
for(int j=0;j<cur.size();j++){
dp[j]=Math.min(dp[j],dp[j+1])+cur.get(j);
}
}
return dp[0];
}
}
发表于 2020-03-19 15:02:27
回复(0)
动态规划，自上而下，设置dp[i][j]表示到达（i,j）位置的最短路径和，最后返回最后一层中最小值。
import java.util.*;
public class Solution {
public int minimumTotal(ArrayList<ArrayList<Integer>> triangle) {
if(triangle==null||triangle.size()<=0)
return 0 ;
ArrayList<ArrayList<Integer>> dp = new ArrayList<ArrayList<Integer>>();
dp.add(triangle.get(0));
for(int i = 1; i <triangle.size(); i++){
ArrayList<Integer> tmp = new ArrayList<Integer>();
for(int j = 0;j < triangle.get(i).size();j++){
int d = Math.min(dp.get(i-1).get(Math.max(j-1,0))+triangle.get(i).get(j),dp.get(i-1).get(Math.min(j,dp.get(i-1).size()-1))+triangle.get(i).get(j));
tmp.add(d);
}
dp.add(tmp);
}
return Collections.min(dp.get(triangle.size()-1));
}
}
发表于 2020-02-15 15:19:04
回复(0)
import java.util.*;
class Solution {
/**
* DP，复用一个长度triangle.size()大小的数组记录
* 上一层元素的构成的小三角的最小路径和,状态转移方程
* f(i,j) = min(f(i+1, j)+triangle[i][j], f(i+1, j+1)+triangle[i][j])
*/
public int minimumTotal(ArrayList<ArrayList<Integer>> triangle) {
if(triangle.size()<1) return 0;
int[] min = new int[triangle.size()];
for(int i=0; i<triangle.size(); i++){
min[i] = triangle.get(triangle.size()-1).get(i);
}
for(int i=triangle.size()-2; i>=0; i--){
for(int j=0; j<=i; j++){
min[j] = Math.min(min[j]+triangle.get(i).get(j),
min[j+1]+triangle.get(i).get(j));
}
}
return min[0];
}
}
发表于 2020-01-08 19:12:01
回复(0)
java实现，已通过。运行时间：54ms，占用内存：10152k。动态规划算法。
题里的矩阵是这样的：
[2]
[3] [4]
[6] [5] [7]
[4] [1] [8] [3]
设从（0，0）到（i,j）的最短路径和为Sum(i,j)，当j != 0和i != j时，(也就是三角形除边以外中间的元素)，到达（i,j）有两种路径，一种是从(i-1,j-1)到（i,j）,另一种是从(i-1,j)到(i,j),
那么Sum(i,j)=min(Sum(i-1,j)+***(i,j),Sum(i-1,j-1)+***(i,j))。
而初始状态是Sum(0,0)=***(i,j)。需要注意的
是，每行第一个，也就j=0，到(i,j)只有一条路径，即：Sum(i,j)=Sum(i-1,0)+***(i,j);还有当i=j，也就是每行最后一个，到（i,j）也是只有一条路径，即：Sum(i,j)=Sum(i-1,i-1)。这两种情况应该分别讨论。
是，每行第一个，也就j=0，到(i,j)只有一条路径，即：Sum(i,j)=Sum(i-1,0)+***(i,j);还有当i=j，也就是每行最后一个，到（i,j）也是只有一条路径，即：Sum(i,j)=Sum(i-1,i-1)。这两种情况应该分别讨论。
最后在Sum(***.size)中找最小值，即为最短路径和。
代码如下：
import java.util.ArrayList;
public class Solution {
public int minimumTotal(ArrayList<ArrayList<Integer>> ***) {
int size=***.size();
int[][]min=new int[size][si***[0][0]=***.get(0).get(0);
int result=0;
for(int i=1;i<size;i++)
{for(int j=0;j<i+1;j++)
if(j>0&&i!=j)
{min[i][j]=Math.min(min[i-1][j-1]+***.get(i).get(j),min[i-1][j]+***.get(i).get(j));}
else{ if(j==0) {min[i][j]=min[i-1][j]+***.get(i).get(j);}
else min[i][j]=min[i-1][j-1]+***.get(i).get(j);}
}
result=min[size-1][0];
for(int m=0;m<size;m++)
{if(min[size-1][m]<result)
result=min[size-1][m];}
return result;
}
}
编辑于 2019-08-15 21:22:24
回复(0)
import java.util.*;
public class Solution {
public int minimumTotal(ArrayList<ArrayList<Integer>> ***) {
int[][] result = new int[***.size()][];
result[0] = new int[1];
result[0][0] = ***.get(0).get(0);
for (int i = 1; i < result.length; i++) {
ArrayList<Integer> temp = ***.get(i);
result[i] = new int[temp.size()];
result[i][0] = result[i - 1][0] + temp.get(0);
for (int j = 1; j < temp.size() - 1; j++) {
result[i][j] = Math.min(result[i - 1][j],result[i - 1][j - 1]) + temp.get(j);
}
result[i][temp.size() - 1] = result[i - 1][result[i - 1].length - 1] + temp.get(temp.size() - 1);
}
int theResult = Integer.MAX_VALUE;
for (int current : result[***.size() - 1]) {
theResult = Math.min(theResult,current);
}
return theResult;
}
}
发表于 2019-07-10 00:42:24
回复(0)
import java.util.ArrayList;//不import 提交就一直报编译错误，行吧
public class Solution {
{
return 0;
for(int j=0;j< curTr.size();j++)
}
}
return dp[0];
}
}
public class Solution {
public int minimumTotal(ArrayList<ArrayList<Integer>> ***) {
//判断三角形为空的情况
if(*** == null || ***.size() == 0){
return 0;
}
//一维数组放每层 每个节点对应路径和的最小值（不断更新，每次只存一层的，其他层的不需要）
int[] dp=new int[***.size()+1];
//从底层往上推
for(int i=***.size()-1;i>=0;i--) {
//存当前行每个数字的值
ArrayList<Integer> curTr=***.get(i);for(int j=0;j< curTr.size();j++)
{
// 最下面那层的DP值其实就是本身的数字，倒数第二层开始DP[j]就是下面相邻2个的最小加上自己。
//这里的dp[j] 使用的时候默认是上一层的，赋值之后变成当前层
dp[j]=Math.min(dp[j],dp[j+1])+curTr.get(j);
}
return dp[0];
}
}
发表于 2019-07-03 13:42:43
回复(0)
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;
public class Bonus {
public int minimumTotal(ArrayList<ArrayList<Integer>> ***) {
if (***.size() == 0)
return 0;
HashMap<Integer, HashMap<Integer, Integer>> map = new HashMap<>();
HashMap<Integer, Integer> rowZero = new HashMap<>();
rowZero.put(0, ***.get(0).get(0));
map.put(0, rowZero);
for (int i = 1; i < ***.size(); i++) {
HashMap<Integer, Integer> thisRow = new HashMap<>();
ArrayList<Integer> list = ***.get(i);
HashMap<Integer, Integer> m = map.get(i - 1);
thisRow.put(0, m.get(0) + list.get(0));
thisRow.put(i, m.get(i - 1) + list.get(i));
map.put(i, thisRow);
}
for (int i = 1; i < ***.size(); i++) {
ArrayList<Integer> list = ***.get(i);
for (int j = 1; j < list.size() - 1; j++) {
HashMap<Integer, Integer> thisRow = map.get(i);
HashMap<Integer, Integer> upperRow = map.get(i - 1);
thisRow.put(j, Math.min(list.get(j) + upperRow.get(j), list.get(j) + upperRow.get(j - 1)));
}
}
int min = Integer.MAX_VALUE;
for (Map.Entry<Integer, Integer> entry : map.get(***.size() - 1).entrySet()) {
min = Math.min(min, entry.getValue());
}
return min;
}
}
发表于 2018-06-09 21:57:06
回复(0)
import java.util.ArrayList;
public class Solution {
public int minimumTotal(ArrayList<ArrayList<Integer>> ***) {
for(int i = ***.size()-1; i > 0; i--){
ArrayList<Integer> list0 = ***.get(i);
ArrayList<Integer> list1 = ***.get(i-1);
for(int j = 0; j < list1.size(); j++){
int min = Math.min(list0.get(j), list0.get(j+1));
list1.set(j, list1.get(j)+min);
}
}
return ***.get(0).get(0);
}
}
发表于 2018-05-04 15:32:11
回复(0)
import java.util.*;
//dp我们从下往上走
//状态转换方程:
//dp[k][i],表示遍历到第k层第i个位置时的最小值
//则当k =len-1时,dp[k][i]=***[len-1][i]，
//当k<len-1时，dp[k][i]=min(dp[k+1][i]+***[k][i],dp[k+1][i+1]+***[len-1][i])
public class Solution {
public int minimumTotal(ArrayList<ArrayList<Integer>> t) {
if(t==null||t.size()==0){
return 0;
}
int len=t.size();
int[] dp=new int[len];
//将最底层的的数据赋给dp数组
for(int i=0;i<len;++i){
dp[i]=t.get(len-1).get(i);
}
for(int i=len-2;i>=0;--i){
//第i层有i+1个元素，数组下标到i
for(int j=0;j<i+1;++j){
dp[j]=Math.min(dp[j]+t.get(i).get(j),dp[j+1]+t.get(i).get(j));
}
}
return dp[0];
}
//dp我们从下往上走
//状态转换方程:
//dp[k][i],表示遍历到第k层第i个位置时的最小值
//则当k =len-1时,dp[k][i]=***[len-1][i]，
//当k<len-1时，dp[k][i]=min(dp[k+1][i]+***[k][i],dp[k+1][i+1]+***[len-1][i])
public class Solution {
public int minimumTotal(ArrayList<ArrayList<Integer>> t) {
if(t==null||t.size()==0){
return 0;
}
int len=t.size();
int[] dp=new int[len];
//将最底层的的数据赋给dp数组
for(int i=0;i<len;++i){
dp[i]=t.get(len-1).get(i);
}
for(int i=len-2;i>=0;--i){
//第i层有i+1个元素，数组下标到i
for(int j=0;j<i+1;++j){
dp[j]=Math.min(dp[j]+t.get(i).get(j),dp[j+1]+t.get(i).get(j));
}
}
return dp[0];
}
}
发表于 2017-12-18 20:14:09
回复(0)
// 贴一个二叉树的思路。
/**
*
* 整个三角形可以看做一个二叉树，用f表示二叉树深度，从1到n。
* 二维ArrayList<ArrayList<Integer>> 可以看做是一个一维数组，其中index表示数组的游标，从0到len-1。
* 左孩子就是当前节点加上这层孩子的数目f，也就是index+f
* len是一维数组，也可以用来约束一维数组的index是否越界，换句话，就是可以判断叶子节点。
*
*/
public class Solution {
int len;
public int minimumTotal(ArrayList<ArrayList<Integer>> ***) {
len = ***.size() * (***.size() + 1) / 2;
return minSum(***, 0, 1);
}
/**
* 用来表示某棵树的路径最小的节点之和，无非两种情况，选择左树或者右树
*/
private int minSum(ArrayList<ArrayList<Integer>> ***, int index, int f) {
if (index >= len) return 0;
int leftVal = minSum(***, index + f, f + 1); //左树的最小路径节点和
int rightVal = minSum(***, index + f + 1, f + 1); //右树的最小路径节点和
List<Integer> list = ***.get(f - 1); //获取层 数组
int val = list.get(index - (f - 1) * f / 2); //换算出在当前数组的位置，根据1...n的连续和公式，前f-1层一共有 (f-1)*f/2个节点
return Math.min(leftVal + val, rightVal + val);
}
}
编辑于 2017-08-31 17:27:08
回复(2)
//遍历被
import java.util.ArrayList;
public class Solution {
private int min=Integer.MAX_VALUE;
public int minimumTotal(ArrayList<ArrayList<Integer>> ***) {
if(***==null){
return 0;
}
minimumTotal(***,0,0,0);
return min;
}
public void minimumTotal(ArrayList<ArrayList<Integer>> ***,int i,int j,int curSum) {
if(i==***.size()){
if(curSum<min){
min=curSum;
}
return ;
}
if(j<0 || j>=***.get(i).size()){
return ;
}
curSum+=***.get(i).get(j);
minimumTotal(***,i+1,j+1,curSum);
minimumTotal(***,i+1,j,curSum);
return;
}
}
发表于 2017-08-12 19:20:08
回复(0)
主要的思路是从上往下，将到每个点的最小路径保存下来，从上到下遍历一遍，在当前点存储最小路径的值，不需要额外的空间，时间复杂度为o(n)，最后在最后一层将最小的点找出来。
public int minimumTotal(ArrayList<ArrayList<Integer>> ***) {
if(***.size() == 0) return 0;
for(int i = 1; i < ***.size(); i++){
ArrayList<Integer> prelist = ***.get(i - 1);
ArrayList<Integer> list = ***.get(i);
//每行第一个点和最后一个点只能从上一行的第一个点及最后一个点走下来
list.set(0,list.get(0) + prelist.get(0));
list.set(list.size() - 1,list.get(list.size() - 1) + prelist.get(prelist.size() - 1));
for(int j = 1; j < list.size() - 1; j++){
//每行其他点判断是从左边的点走下来还是从右边的点走下来
list.set(j,Math.min(list.get(j) + prelist.get(j - 1),list.get(j) + prelist.get(j)));
}
}
ArrayList<Integer> list = ***.get(***.size() - 1);
int min = Integer.MAX_VALUE;
for(int num : list){
min = min < num ? min : num;
}
return min;
}
发表于 2017-08-03 15:16:48
回复(0)
import java.util.*;
public class Solution {
public static int minimumTotal(ArrayList<ArrayList<Integer>> ***) {
if (*** == null || ***.size() == 0)
return 0;
List<Integer> midList = new ArrayList<Integer>(***.get(***.size() - 1));
for (int i = ***.size() - 2; i >= 0; --i) {
for (int j = 0; j < ***.get(i).size(); ++j) {
midList.set(j, Math.min(midList.get(j), midList.get(j + 1)) + ***.get(i).get(j));
}
}
return midList.get(0);
}
}
发表于 2017-07-31 21:19:05
回复(0)
import java.util.*;
public class Solution {
public int minimumTotal(ArrayList<ArrayList<Integer>> ***) {
if(***==null||***.get(0)==null||***.size()<1||***.get(0).size()<1)
return 0;
ArrayList<Integer> last=new ArrayList<Integer>();
last.add(0);
ArrayList<Integer> cur;
int res=Integer.MAX_VALUE;
for(ArrayList<Integer> list:***){
cur=new ArrayList<Integer>();
for(int i=0;i<list.size();i++){
int val=Math.min((i-1)>=0?last.get(i-1):Integer.MAX_VALUE,i<last.size()?last.get(i):Integer.MAX_VALUE)+list.get(i);
cur.add(val);
}
last=cur;
}
for(int num:last){
res=Math.min(res,num);
}
return res;
}
}
发表于 2017-05-23 19:46:54
回复(0)
int len = ***.size();
int[] minArray = new int[len];
ArrayList<Integer> temp = ***.get(len-1);
for(int i=0;i<len;i++){
minArray[i] = temp.get(i);
}
for(int i=1;i<len;i++){
temp = ***.get(len-i-1);
for(int j=0;j<=len-i-1;j++){
minArray[j] = Math.min(minArray[j], minArray[j+1])+temp.get(j);
}}return minArray[0];
发表于 2017-03-21 10:01:12
回复(0)
public class Solution { public int minimumTotal(List<List<Integer>> ***) { for(int i = ***.size() - 2; i >= 0; i--) for(int j = 0; j <= i; j++) ***.get(i).set(j, ***.get(i).get(j) + Math.min(***.get(i + 1).get(j), ***.get(i + 1).get(j + 1))); return ***.get(0).get(0); } }
发表于 2017-03-11 23:25:46
回复(0)
问题信息
难度：
23条回答
123收藏
31026浏览
通过挑战的用户
查看代码-
2023-03-14 16:32:43 -
2023-03-06 22:11:40 -
2023-03-04 15:45:07 -
2022-12-31 13:39:08
-
2022-12-06 15:06:43
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
