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

三角形最小路径和

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]

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

尝试动态规划

全部评论

相关推荐

不愿透露姓名的神秘牛友
昨天 14:00
林子大了什么鸟都有啊,我觉得我说的已经很客气了,阴阳谁呢
牛客62656195...:应该不是阴阳吧?你第一次注册的时候boss就说你是牛人
点赞 评论 收藏
分享
Twilight_m...:经典我朋友XXXX起手,这是那种经典的不知道目前行情搁那儿胡编乱造瞎指导的中年人,不用理这种**
点赞 评论 收藏
分享
05-20 13:59
门头沟学院 Java
米黑子米黑子:你这个成绩不争取下保研?
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
昨天 11:31
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

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