首页 > 其他分享 >三角形最小路径和

三角形最小路径和

时间:2024-04-27 15:00:12浏览次数:25  
标签:triangle min int 路径 List 最小 range 三角形 dp

题源:IOI飞入寻常百姓家

class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        n = len(triangle)
        dp = [[0] * (i + 1) for i in range(n)]

        dp[0][0] = triangle[0][0]

        for i in range(1, n):
            dp[i][0] = dp[i - 1][0] + triangle[i][0]
            dp[i][i] = dp[i - 1][i - 1] + triangle[i][i]

            for j in range(1, i):
                dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j]) + triangle[i][j]

        return min(dp[n - 1])

状态转移方程dp[i][j] = min(dp[i-1][j-1], dp[i-1][j]) + triangle[i][j],非常的直观,但是需要主要边界条件需要注意,即dp[i][0]和dp[i][i]的取值是固定的,需要在进行每一层的dp之前/后额外写代码完成初始化,以免出现边界条件问题

优化成空间复杂度O(N)的方法:

只需要维护两行的状态,而不是整个三角形的状态。我们可以使用两个一维数组,分别表示当前行和上一行的状态

class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        n = len(triangle)
        dp = [0] * n

        dp[0] = triangle[0][0]

        for i in range(1, n):
            dp[i] = dp[i - 1] + triangle[i][i]  # 更新最右侧元素

            for j in range(i - 1, 0, -1):
                dp[j] = min(dp[j - 1], dp[j]) + triangle[i][j]

            dp[0] = dp[0] + triangle[i][0]  # 更新最左侧元素

        return min(dp)

标签:triangle,min,int,路径,List,最小,range,三角形,dp
From: https://www.cnblogs.com/peterzh/p/18162069

相关文章

  • 在 windows 上运行的 podman 默认的挂载相对路径是什么
    我在windows运行podman当成docker的代替品,从网上抄了ollama的部署命令,发现里面存在一个相对路径的挂载文件夹。我期望拿到ollama的下载内容,需要寻找到podman默认的挂载路径,但在网上找了一圈,可能是我的关键词问题,没有找到,于是记录本文期望能帮到大家如下面命令podman......
  • dotnet C# 使用 Win32 函数获取用户下载文件夹的路径的方法
    大家都知道,在dotnet里面的可以使用Environment.GetFolderPath方法配合Environment.SpecialFolder枚举列出当前运行环境下的一些特殊文件夹。然而SpecialFolder枚举不包含对Download下载文件夹的枚举值,如咱需要获取用户当前的下载文件夹,需要使用Win32方法来辅助获取在......
  • Visual Studio 项目发布时将资源目录文件夹所有文件拷贝到发布路径
    1.背景在.NET项目开发过程中,时常需要将资源文件夹复制到生成目录,以确保这些资源随项目输出。2.方法找到当前项目例如:xxxxx.Api 双击进入,对 .csproj文件内容,加入如下信息:<TargetName="CopyResourcesPublish"AfterTargets="Publish"><ItemGroup><Resource......
  • Electron打包的时候路径出现问题!include: could not find: "C:\Users\xxxx\AppDat
    !include:couldnotopenfile:"C:\ztg\projects\electron-vite-vue-ts\node_modules\.pnpm\[email protected][email protected][email protected]_dmg-bui_lrspnoputfiosacwyigcypdbdi\node_modules\app-builder-lib\t......
  • 配置别名路径联想:@代替.src
    在根目录下键jsconfig.json里面写{{"compilerOptions":{"baseUrl":"./","paths":{"@/*":["src/*"]}}}}/*只有联想的作用*/上面只有联想作用真正做到转换的在vite.config.js import{fileURL......
  • 欧拉路径&&欧拉回路
    定义:欧拉路径:指图中的一条路径,使得所有边都被经过且只经过一次欧拉回路:指图中的一条欧拉路径,且起点和终点相同。欧拉图:指有欧拉回路的图半欧拉图:指有欧拉路径但没有欧拉回路的图性质:1.如果一个无向图是欧拉图,那么所有节点的度数均为偶数2.如果一个无向图是半欧拉图,那么除了......
  • 网络隔离的最小配置
    作者:任云康,青云科技研发工程师前言对于项目下的网络隔离,有用户提出了以下疑问:网络隔离是针对Pod的吗?网络隔离的最小配置是什么?配置后,哪些是可以访问的,哪些是不可以访问的?通过Ingress暴露、LB类型的Service暴露、NodePort类型的Service暴露的流量的具体链路是......
  • 项目管理中,为什么关键路径是完成项目的最短时间?
    关键路径方法(CriticalPathMethod)应用于项目管理中,使用该方法可以计算出完成项目所需的最短时间,在理想情况下,至少需要这么长的时间才能完成该项目。关键路径由一系列关键节点组成,这些节点的有序排列构成了关键路径。每个关键节点都是该项目中的其中一个任务,而每个任务包括任务......
  • 项目管理中,为什么关键路径是完成项目的最短时间?
    关键路径方法(CriticalPathMethod)应用于项目管理中,使用该方法可以计算出完成项目所需的最短时间,在理想情况下,至少需要这么长的时间才能完成该项目。关键路径由一系列关键节点组成,这些节点的有序排列构成了关键路径。每个关键节点都是该项目中的其中一个任务,而每个任务包括任务......
  • vscode 提示导入的第三方包 路径不正确 ,要怎么解决?
    问题:vscode提示导入的第三方包路径不正确,如:import{Modal}from"node_modules/antd/lib/index";应该是import{Modal}from"antd";要怎么解决?回答要让VSCode在自动导入时不使用node_modules的完整路径,可按以下步骤操作:打开VSCode进入设置页面,你可以通过顶部菜......