首页 > 试题广场 >

三角形最小路径和

[编程题]三角形最小路径和
  • 热度指数:7228 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
给定一个正三角形数组,自顶到底分别有 1,2,3,4,5...,n 个元素,找出自顶向下的最小路径和。

每一步只能移动到下一行的相邻节点上,相邻节点指下行种下标与之相同或下标加一的两个节点。

数据范围:三角形数组行数满足 ,数组中的值都满足

例如当输入[[2],[3,4],[6,5,7],[4,1,8,3]],对应的输出为11,
所选的路径如下图所示:

示例1

输入

[[10]]

输出

10
示例2

输入

[[2],[3,4],[6,5,7],[4,1,8,3]]

输出

11

说明

最小路径是 2 , 3 ,5 , 1  
示例3

输入

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

发表于 2021-12-02 16:03:54 回复(0)
从下往上原地动态规划,将原始的triangle数组视为dp数组。dp[i][j]表示从最底层的三角形累加到triangle[i][j]时所得到的最小值,因此它的值应该为triangle[i][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];
    }
}

发表于 2021-12-17 10:24:08 回复(0)
从上往下动态规划,注意三角的左边只由上它的上一个状态推出,斜边只由其左上边推出。
初始状态:dp[0][0] = triangle[0][0];
左边:dp[i][0] = dp[i - 1][0] + triangle[i][0];
斜边:dp[i][i] = dp[i - 1][i - 1] + triangle[i][i];
其他:dp[i][j] = triangle[i][j] + min(dp[i - 1][j], dp[i - 1][j - 1]);
最后找出dp最小路径
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;
    }


发表于 2022-04-24 17:10:15 回复(0)
#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;
    }
};

编辑于 2023-12-27 16:11:15 回复(0)
#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;
    }
};

发表于 2023-07-26 17:18:48 回复(0)
#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];
    }
};

发表于 2023-05-22 19:56:00 回复(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;
    }
}

发表于 2023-05-17 11:25:53 回复(0)
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]

发表于 2023-03-16 16:00:44 回复(0)
/**
 * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
 *
 *
 * @param triangle int整型二维数组
 * @param triangleRowLen int triangle数组行数
 * @param triangleColLen int* triangle数组列数
 * @return int整型
 */
 int min(int a,int b)
 {
    return a<b?a:b;
 }//取a,b中最小值
int minTrace(int** triangle, int triangleRowLen, int* triangleColLen )
{
    for(int row=triangleRowLen-2;row>=0;row--)//从倒数第二行开始,从0开始记
    {
        for(int col=0;col<=row;col++)
        {
          triangle[row][col]+=min(triangle[row+1][col],triangle[row+1][col+1]);
        }//triangle[row][col]表示从triangle[row][col]开始到最后一行中一个数总和中的最小和
    }
    return triangle[0][0];
}
/* 例如    
2     从倒数第二行第一个数6开始,triangle[2][0]=6+min{4,1},因为4<1,所以triangle[2][0]=7
3 4   以此类推 triangle[2][1]=6,triangle[2][2]=10
6 5 7                                                                                            
4 1 8 3 上升一行row-1,triangle[1][0]=3+min(triangle[2][0],triangle[2][1]),因为6<10,所以triangle[1][0]=9,triangle[1][1]=10,
         上升一行row-1,triangle[0][0]=2+triangle[1][0]=11
         

*/
发表于 2023-01-10 17:48:48 回复(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;
    }
}

发表于 2023-01-08 16:54:59 回复(0)
/**
 * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
 *
 * 
 * @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
};

发表于 2022-11-30 19:47:45 回复(0)
自底向上,逐层求解每个值,顶层值即为最小值
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];
    }
}


发表于 2022-11-13 11:21:02 回复(0)
Python
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。

发表于 2022-08-18 23:53:31 回复(1)
class Solution:
    def minTrace(self , triangle: List[List[int]]) -> int:
        # write code here
        n=len(triangle)
        ans=[[0]*(i+1) for i in range(n)]
        ans[0][0]=triangle[0][0]
        for i in range(1,n):
            for j in range(i+1):
                if i==0 and j==0:
                    continue
                elif i==j:
                    ans[i][j]=ans[i-1][j-1]+triangle[i][j]
                elif j==0:
                    ans[i][j]=ans[i-1][j]+triangle[i][j]
                else:
                    ans[i][j]=triangle[i][j]+min(ans[i-1][j],ans[i-1][j-1])
        return min(ans[-1])
发表于 2022-04-26 19:33:21 回复(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; 
        }    
    }
}

发表于 2022-04-11 11:29:45 回复(1)
#
class Solution:
    def minTrace(self , triangle: List[List[int]]) -> int:
        # write code here
        m=len(triangle)-1
        while m>0:
            for j in range(m):
                triangle[m-1][j]=min(triangle[m][j],triangle[m][j+1])+triangle[m-1][j]
            m-=1
        return triangle[0][0]

发表于 2022-01-23 07:49:20 回复(0)