首页 > 试题广场 >

三角形最小路径和

[编程题]三角形最小路径和
  • 热度指数：13034 时间限制：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
算法知识视频讲解
添加回答
C
cs小白_头像 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)
C
terirx头像 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)
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)
提交观点

问题信息

动态规划 数组
难度：
3条回答 3541浏览

热门推荐

通过挑战的用户

查看代码

相关试题

三角形最小路径和

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号