首页 > 试题广场 >

三角形最小路径和

[编程题]三角形最小路径和
  • 热度指数：7549 时间限制：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
希望被捞的小熊猫很想奋斗头像 希望被捞的小熊猫很想奋斗
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @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)
提交观点

问题信息

动态规划 数组
难度：
1条回答 2028浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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