三角形最小路径和_

Java

pein531

从下往上原地动态规划，将原始的triangle数组视为dp数组。dp[i][j]表示从最底层的三角形累加到triangle[i][j]时所得到的最小值，因此它的值应该为triangle[i][j]加上它正下方和右下方中小的那个，状态转移方程为：

$dp_{i,j}=triangle_{i,j}+min(dp_{i+1,j},dp_{i+1,j+1})$

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 回复(1)

C++

紧张的花生米在写日记

从上往下动态规划，注意三角的左边只由上它的上一个状态推出，斜边只由其左上边推出。

初始状态：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)

C++

defaulter

int minTrace(vector<vector<int>> &triangle) // 二维数组
    {
        // write code here
        int m = triangle.size();                      // 行数
        vector<vector<int>> dp(m, vector<int>(m, 0)); // 创建二维数组容器，并初始化为0
        dp[0][0] = triangle[0][0]; // 确定边界值                   // 初始化起点
        for (int i = 1; i < m; i++)
        {
            for (int j = 0; j <= i; j++)//二维数组的话一般都是两层for循环遍历所有数据
            {
                if (j == 0)//前两部判断都是为了确定边界值，因为只有一行或一列，所以不需要考虑边界值
                    dp[i][j] = dp[i - 1][j] + triangle[i][j];
                else if (j == i)
                    dp[i][j] = dp[i - 1][j - 1] + triangle[i][j];
                else
                    dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - 1]) + triangle[i][j];
            }
        }
        int res = 1e9;
        for (int i = 0; i < m; i++)
        {
            res = min(res, dp[m - 1][i]);
        }
        return res;
    }

发表于 2025-02-26 16:41:44 回复(0)

唐氏综合征

正常解法：自上而下构建dp数组, dp[i][j] 表示第 i 层选择元素为 triangle[i][j]

状态转移三种可能：

1. i 层第一个元素只能是正上方转移过来

2. i 层第 i 个元素只能是 i-1 层 i-1 个元素转移过来

3. 其他是 1,2 中两种可能取其小

最后遍历最后一层找到最小值即为全局最小值

 public static int minTrace(int[][] triangle) {
        // write code here
        if (triangle.length == 1) return triangle[0][0];
        // dp[i][j] 表示第 i 层选 triangle[i][j] 时的最小值
        int[][] dp = new int[triangle.length][triangle.length];
        dp[0][0] = triangle[0][0];
        dp[1][0] = dp[0][0] + triangle[1][0];
        dp[1][1] = dp[0][0] + triangle[1][1];

        // 当第 i 层时, 纵坐标最多为 i
        for (int i = 2; i < triangle.length; i++) {
            // 不能记录某一层的最小值是因为当层数增加时，该最小值就不是全局最小值
            for (int j = 0; j <= i; j++) {
                // 第一个元素，则只能是正上方转移过来
                if (j == 0) dp[i][j] = triangle[i][j] + dp[i - 1][0];
                // 最后一个元素，只能是左上角转移过来
                else if (j == i) dp[i][j] = triangle[i][j] + dp[i - 1][j - 1];
                // 其余两种可能
                else dp[i][j] = triangle[i][j] + Math.min(dp[i - 1][j - 1], dp[i - 1][j]);
            }
        }
        // 从最后一层找到最终最小值
        int res = Integer.MAX_VALUE;
        for (int i = 0; i < dp[dp.length - 1].length; i++) {
            res = Math.min(res, dp[dp.length - 1][i]);
        }
        return res;
    }

发表于 2024-11-06 23:31:33 回复(0)

Java

梁山教父

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 回复(1)

C++

牛客517918718号

     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 回复(1)

C++

想五点下班勇士希望奇迹发生

5行解决。
int minTrace(vector<vector<int> >& triangle) {
int n=triangle.size();
for(int i=n-1;i>0;i--)
for(int j=i-1;j>=0;j--)
triangle[i-1][j]+=min(triangle[i][j],triangle[i][j+1]);
return triangle[0][0];
}

发表于 2025-07-18 17:25:00 回复(0)

牛客947103413号

class Solution {
  public:
    void sol(vector<vector<int> >&  tri, int i, int j,  int& cur,
             vector<int>& all_path) {

        if (i == tri.size() - 1) {
            all_path.push_back(cur);
            return;
        }
        cur += (tri[i + 1][j]);
        sol(tri, i + 1, j, cur, all_path);
        cur -= (tri[i + 1][j]);

        cur += (tri[i + 1][j + 1]);
        sol(tri, i + 1, j + 1, cur, all_path);
        cur -= (tri[i + 1][j + 1]);
    }
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param triangle int整型vector<vector<>>
     * @return int整型
     */
    int minTrace(vector<vector<int> >& triangle) {
        // write code here
        int cur=0;
        cur += (triangle[0][0]);
        vector<int> all_path;
        sol(triangle, 0, 0, cur, all_path);

        // cout << "sum.size()=" << all_path.size();
        sort(all_path.begin(), all_path.end());
        return all_path.front();
    }
};
请教大佬为什么会超内存呢

发表于 2025-05-16 16:32:16 回复(0)

Fine_Motion

题目：val<=10^4

用例有个点是1000000000

神人范围哈哈

发表于 2025-04-19 11:40:01 回复(0)

Python 3

牛客78232076号

from re import S
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param triangle int整型二维数组
# @return int整型
#
class Solution:
    def minTrace(self , triangle: List[List[int]]) -> int:
        # write code here
        sum=triangle[0][0]
        cue=triangle[0][0]
        if len(triangle)==1:
            sum=triangle[0][0]
        elif len(triangle)==0:
            return 0
        else:
            for i in range(len(triangle)-1):
                index=triangle[i].index(cue)
                left=triangle[i+1][index]
                right=triangle[i+1][index+1]
                cue=min(left,right)
                sum=sum+cue
        return sum

看看有什么问题

发表于 2024-12-08 12:09:42 回复(0)

C

cs小白_

int minTrace(int** triangle, int triangleRowLen, int* triangleColLen ) {
    int dp[201][200];
    dp[0][0]=triangle[0][0];
    for (int i=1; i<triangleRowLen; i++) {
           dp[i][0]=dp[i-1][0]+triangle[i][0];
    }
    for (int i=1; i<triangleRowLen; i++) {
        for (int j=1; j<triangleColLen[i]; j++) {
             if (j==triangleColLen[i]-1) {
                 dp[i][j]=dp[i-1][j-1]+triangle[i][j];
             }
             else {
                 dp[i][j]=(dp[i-1][j-1]<dp[i-1][j]?dp[i-1][j-1]:dp[i-1][j])+triangle[i][j];
             }
        }
    }
    int min=dp[triangleRowLen-1][0];
    for (int i=0; i<triangleColLen[triangleRowLen-1]; i++) {
         if(dp[triangleRowLen-1][i]<min){
            min=dp[triangleRowLen-1][i];
         }
    }
    return min;
    
}

发表于 2024-11-29 19:38:52 回复(0)

张润丰

下一层每个元素的最小值均由上一层每个元素的最小值得出，然后递归就行了

function minTrace( triangle ) {
    // write code here
    let results=[triangle[0][0]]
    let len=triangle.length
    for(let i=1;i<len;i++){
        let res=[]
        triangle[i].forEach((item,j)=>{
            const stepLen=triangle[i].length-1
            if(j===0){
                res.push(results[0]+item)
            }else if(j===stepLen){
                const lastStepLen=results.length-1
                res.push(results[lastStepLen]+item)
            }else{
                res.push(Math.min(results[j],results[j-1])+item)
            }
        })
        results=res
    }
    return Math.min(...results)
}

发表于 2024-11-03 13:19:22 回复(0)

双非小牛马hh

#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param triangle int整型vector<vector<>> 
     * @return int整型
     */
    int minTrace(vector<vector<int> >& triangle) {
        // write code here
        // 总行数
        int n=triangle.size();
        for(int i=n-2;i>=0;i--){
            for(int j=triangle[i].size()-1;j>=0;j--){
                triangle[i][j]+=min(triangle[i+1][j],triangle[i+1][j+1]);
            }
        }
        return triangle[0][0];
    }
};

发表于 2024-08-29 22:03:07 回复(1)

C

terirx

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param triangle int整型二维数组 
 * @param triangleRowLen int triangle数组行数
 * @param triangleColLen int* triangle数组列数
 * @return int整型
 */
int minTrace(int** triangle, int triangleRowLen, int* triangleColLen ) {
    int dp[201][200] = {0};
    int min=0;
    dp[0][0] = triangle[0][0];
    //先记录整个第一列的dp值
    for(int i=1; i<triangleRowLen; i++)
        dp[i][0] = dp[i-1][0] + triangle[i][0];
    //然后每一个数都是起点到该店的最小路径，为上一个或前一个的最小路径加上自己
    for(int i=1; i<triangleRowLen; i++)
    {
        for(int j=1; j<(triangleColLen[triangleRowLen-1]); j++)
        {
            if(j == triangleColLen[i]-1)
            {
                dp[i][j] = dp[i-1][j-1]+triangle[i][j];
                continue;
            }
            min = dp[i-1][j]<dp[i-1][j-1]?dp[i-1][j]:dp[i-1][j-1];
            dp[i][j] = min+triangle[i][j];
        }
    }
    min = dp[triangleRowLen-1][0];
    for(int j=0; j<(triangleColLen[triangleRowLen-1]); j++)
    {
        if(dp[triangleRowLen-1][j]<min)
        min = dp[triangleRowLen-1][j];
    }
    return min;
    // write code here
}

发表于 2024-08-19 14:56:58 回复(0)

Python3

liangzhengjie

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param triangle int整型二维数组 
# @return int整型
#
class Solution:
    def minTrace(self , triangle: List[List[int]]) -> int:
        # write code here
        dp = triangle.copy()

        for i in range(1, len(triangle)):
            for j in range(len(triangle[i])):
                if j == len(triangle[i]) - 1:
                    dp[i][j] = dp[i-1][j-1] + triangle[i][j]
                elif j == 0:
                    dp[i][j] = dp[i-1][j] + triangle[i][j]
                else:
                    dp[i][j] = min(dp[i-1][j-1], dp[i-1][j]) + triangle[i][j]

        return min(dp[-1])

编辑于 2024-04-23 22:08:57 回复(0)

牛客212561046号

#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)

C++

牛客530877384号

#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)

C++

牛客220644275号

#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)

Python3

Namely

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)

C

希望被捞的小熊猫很想奋斗

/**

* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可

*

* @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)

三角形最小路径和

输入

输出

输入

输出

说明

输入

输出

问题信息

热门推荐

通过挑战的用户

相关试题