题解 | #三角形最小路径和#

三角形最小路径和

https://www.nowcoder.com/practice/c9d44b73dc7c4dbfa4272224b1f9b42c

import traceback
from sys import flags
from itertools import count
#
# 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
#
# 
# @param triangle int整型二维数组 
# @return int整型
#
class Solution:
    def minTrace(self , triangle: List[List[int]]) -> int:
        # write code here
        # 递归不好做
        n = len(triangle)
        if n ==1:
            return triangle[0][0]
        #第n-1的值更改为:
        for i in range(0,n-1):
            for j in range(0,n-1-i):
                triangle[n-2-i][j] = triangle[n-2-i][j]+min(triangle[n-1-i][j],triangle[n-1-i][j+1])

        return triangle[0][0]

这一题看起来挺简单的,做起来觉得挺难的,一开始想着递归,后来发现怎么这么复杂,不是递归能做出来的

尝试动态规划

全部评论

相关推荐

不愿透露姓名的神秘牛友
07-11 11:00
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-08 13:05
点赞 评论 收藏
分享
05-19 15:21
已编辑
门头沟学院 Java
白火同学:你才沟通了200,说实话,北上广深杭这里面你连一座城市的互联网公司都没投满呢,更别说还有各种准一线二线城市了。等你沟通突破了三位数,还没结果再考虑转行的事吧。
点赞 评论 收藏
分享
fRank1e:吓得我不敢去外包了,但是目前也只有外包这一个实习,我还要继续去吗
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务