首页 > 其他分享 >动态规划--三角形最小路径和

动态规划--三角形最小路径和

时间:2024-10-04 12:00:47浏览次数:6  
标签:结点 triangle min -- sum 路径 下标 三角形 append

问题描述

给定一个三角形 triangle ,找出自顶向下的最小路径和。

每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说,如果正位于当前行的下标 i ,那么下一步可以移动到下一行的下标 i 或 i + 1 。

示例 1:

输入: triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
输出: 11
解释: 如下面简图所示: 2 3 4 6 5 7 4 1 8 3 自顶向下的最小路径和为 11(即,2 + 3 + 5 + 1 = 11)。

示例 2:

输入: triangle = [[-10]]
输出: -10

代码


class Solution(object):
    def minimumTotal(self, triangle):
        """
        :type triangle: List[List[int]]
        :rtype: int
        """
        min_sum = []
        for i in range(len(triangle)):
            sum_i_min = []
            if i == 0:
                sum_i_min.append(triangle[i][0])

            else:
                for j in range(len(triangle[i])):
                    if j == 0:
                        print(sum_i_min)
                        sum_i_min.append(triangle[i][j] + min_sum[i-1][j])
                    elif j == len(triangle[i]) - 1:
                        sum_i_min.append(triangle[i][j] + min_sum[i-1][j-1])
                    else:
                        sum_i_min.append(min(triangle[i][j] + min_sum[i-1][j-1], triangle[i][j] + min_sum[i-1][j]))
            min_sum.append(sum_i_min)
        return min(min_sum[-1])

标签:结点,triangle,min,--,sum,路径,下标,三角形,append
From: https://www.cnblogs.com/jackchen28/p/18446482

相关文章

  • 代码随想录算法训练营 | 134. 加油站,135. 分发糖果,860.柠檬水找零,406.根据身高重建队
    134.加油站题目链接:134.加油站文档讲解︰代码随想录(programmercarl.com)视频讲解︰加油站日期:2024-10-04想法:1.总汽油大于等于消耗一定能跑完,2.当前剩余汽油小于0了,只能从下一站开始重新计算Java代码如下:classSolution{publicintcanCompleteCircuit(int[]gas,int......
  • Introduction to X86-64 Assembly Programming
    Project3:IntroductiontoX86-64AssemblyProgrammingGradingFormGoalInthisprojectyouwillwriteprogramsinx86-64assemblylanguage.Itisimportantthatyoulearnthex86-64assemblylanguagesinceitistheoneyouuseeverydayinyourPC,Ma......
  • R语言中gene symbol 转换为ENTREZID, clusterprofile富集分析
    001、genes<-read.table("genes.txt")##读取基因symbolhead(genes)tail(genes)genes<-genes[genes!="NA_NA"&genes!="unknow",,drop=FALSE]##去除无效信息(可选)genes_list<-unique(ge......
  • Restore .bacpac file to DEV VM D365 FO
    Restore.bacpacfiletoDEVVMD365FO Restore.bacpacfiletoDevelopmentVMSteps: 1.       TakeBackupofAxDBdatabasefromDevelopmentVM 2.       OpenCommandPrompt(RunasAdministrator)GoToPath(VersionFoldermightbedif......
  • Leetcode 1498. 满足条件的子序列数目
    1.题目基本信息1.1.题目描述给你一个整数数组nums和一个整数target。请你统计并返回nums中能满足其最小元素与最大元素的和小于或等于target的非空子序列的数目。由于答案可能很大,请将结果对109+7取余后返回。1.2.题目地址https://leetcode.cn/problems/num......
  • UR #1
    A.缩进优化题目描述有\(N\)行,每行有\(A_i\)个空格。你可以选择一个默认TAB长度\(x\)。并用一个TAB替换\(x\)个空格。求最终需要TAB和空格数量之和的最小值。思路我们先对值的出现次数做一个前缀和,然后枚举\(x\)。并枚举\(x\)的倍数再统计答案即可。这样是一......
  • Log 工具打印日志
    Android采用Log工具打印日志,它将各类日志划分为五个等级:Log.e:表示错误信息,比如可能导致程序崩溃的异常.Log.w:表示警告信息.Log.i:表示一般消息.Log.d:表示调试信息,可把程序运行时的变量值打印出来,方便跟踪调试.Log.v:表示冗余信息.如果设置e的话,后......
  • 1
    #include#include#include#include#include#includeusingnamespacestd;#defineTIMERintclock_tstart,end;structmodule{ stringtitle; TIMERteamA,teamB; module*next=nullptr; module*pre=nullptr;}*Begin=newmodule,*handle......
  • Nuxt.js 应用中的 app:beforeMount 钩子详解
    title:Nuxt.js应用中的app:beforeMount钩子详解date:2024/10/4updated:2024/10/4author:cmdragonexcerpt:app:beforeMount是一个强大的钩子,允许开发者在用户界面挂载前控制应用的初始化过程。通过有效利用这一钩子,我们可以优化应用的用户体验,保持状态一致性并高效......
  • android 反编译
    https://juejin.cn/post/6844903821257211911?searchId=202410031145152AA4BB76BB0670AB5957android:screenOrientation="landscape"apktoolempty-framework-dir--force//APKTool反编译apktoold-f1.apk//apktool编译:编译修改后的代码生成新的apkapktoolb1-onew.a......