文档章节

120三角形最小路径之和

o
 osc_o9u1um45
发布于 07/01 09:08
字数 352
阅读 25
收藏 0

精选30+云产品,助力企业轻松上云!>>>

from typing import List
class Solution:
def minimumTotal1(self, triangle: List[List[int]]) -> int:
return self.dfs(triangle,0,0,len(triangle),0)
# 深搜的做法,这个做法是错误的,
# 我本来的想法是按照遍历每一层的最小值。但是是行不通的
def dfs(self,num_list,position,depth,maxdepth,min_sum):
# 递归函数的出口
if depth == maxdepth:
return min_sum
# 列表的第一层只有一个数。
if depth == 0:
min_sum += num_list[depth][position]
return self.dfs(num_list,position,depth + 1,maxdepth,min_sum)
# 后边分三种情况讨论,
if depth != 0:
if num_list[depth][position] > num_list[depth][position + 1]:
min_sum += num_list[depth][position + 1]
position += 1
return self.dfs(num_list,position,depth + 1,maxdepth,min_sum)
elif num_list[depth][position] < num_list[depth][position + 1]:
min_sum += num_list[depth][position]
return self.dfs(num_list,position,depth + 1,maxdepth,min_sum)
else:
min_sum1 = self.dfs(num_list,position,depth + 1,maxdepth,min_sum)
min_sum2 = self.dfs(num_list,position + 1,depth + 1,maxdepth,min_sum)
if min_sum1 > min_sum2:return min_sum2
else:return min_sum1
# 正确的做法是使用动态规划的方法。
# 计算出每一条路径的最小值
def minimumTotal(self, triangle: List[List[int]]) -> int:
# 进行双重循环遍历,
for index1 in range(1,len(triangle)):
for index2 in range(index1 + 1):
# 每层列表开头和结尾,只可能是上一层列表的开头结尾走到。
if index2 == 0:
triangle[index1][index2] += triangle[index1 - 1 ][index2]
elif index1 == index2:
triangle[index1][index2] += triangle[index1 - 1][index2 - 1]
# 每一层其他位置只可能由上一层的当前位置和左边一个位置走到
else:
triangle[index1][index2] += min(triangle[index1 -1][index2],triangle[index1 - 1][index2 - 1])
return min(triangle[-1])
A = Solution()
print(A.minimumTotal([[2],
[3,4],
[6,5,7],
[4,1,8,3]]))

























































o
粉丝 0
博文 50
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。
Leetcode【120、611、813、915】

问题描述:【DP】120. Triangle 解题思路: 这道题是给一个三角形,从顶到下计算最小路径和。 容易想到用动态规划求解,dp[i][j] 存储累加到位置 (i, j) 的最小路径和。 如果是从顶到下,那么...

牛奶芝麻
2019/07/11
0
0
算法学习——动态规划之点数值三角形的最小路径

算法描述 在一个n行的点数值三角形中,寻找从顶点开始每一步可沿着左斜或者右斜向下直到到达底端,使得每个点上的数值之和为最小 右图为一个4行的点数值三角形 算法思路 接收用户输入行数n 使...

Stars-one
2018/11/13
0
0
算法52-----矩阵最小路径【动态规划】

一、题目:矩阵最小路径 给定一个包含非负整数的 m x n 网格,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。 说明:每次只能向下或者向右移动一步。 示例: 输入:[ [1,3,1...

osc_rhtu94s6
2018/11/17
4
0
leetcode常见算法与数据结构汇总

leetcode刷题之后,很多问题老是记忆不深刻,因此特意开此帖: 一、对做过题目的总结; 二、对一些方法精妙未能领会透彻的代码汇总,进行时常学习; 三、总结面试笔试常见题目,并讨论最优解...

osc_3dxe2p2c
2019/04/02
19
0
LeetCode 120. 三角形最小路径和(Triangle)

题目描述 给定一个三角形,找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。 例如,给定三角形: [ [6,5,7],[4,1,8,3]] 自顶向下的最小路径和为 (即,2 + 3 + 5 + 1 = 1...

osc_9ipdey7e
2018/05/21
2
0

没有更多内容

加载失败,请刷新页面

加载更多

测试工程师需要了解的shell变量知识

顾老师安全测试新课,报名地址: http://www.hbz100.com/pc/course/courseInfo.do?courseId=182320200226121405459。疫情期间,您在注意身体安全的同时,关注身体安全了吗?500元工作几天的薪...

啄木鸟顾老师
04/15
13
0
前端面试开源项目清单(github仓库,个人网站都有)

 复习前端面试的知识,是为了巩固前端的基础知识,最重要的还是平时的积累! ” 开源项目 https://github.com/InterviewMap/CS-Interview-Knowledge-Map 建立最好的面试地图。目前的内容包...

Fe-frank
05/11
12
0
【Flutter 专题】33 自定义 View 之 Canvas (一)

和尚最近在学习自定义 View,刚了解了一下 Paint 画笔的神奇之处,现在学习一下 Canvas 画布的神秘之处。Flutter 提供了众多的绘制方法,和尚接触不深,尽量都尝试一下。 Canvas 画布 drawCo...

阿策
2019/02/26
15
0
程序员,有需求做需求,有bug改bug,有什么好生气的呢?

对哦,我有什么好生气的呢! 本文分享自微信公众号 - WriteSimpleDemo(this_is_a_wechat)。 如有侵权,请联系 support@oschina.cn 删除。 本文参与“OSC源创计划”,欢迎正在阅读的你也加入...

PedroQin
2019/10/25
8
0
[从0到1搭建ABP微服务] - 搭建授权服务

一、简介 授权中心是微服务架构中最为核心重要的环节,不仅为web、app等客户端提供身份授权服务,还对其他微服务提供身份认证服务。ABP微服务架构中使用identityServer4框架进行身份管理,并...

osc_g91p39eg
23分钟前
14
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部