LeetCode每日一练——三角形最小路径和

示例：

给定一个三角形，找出自顶向下的最小路径和，每一步只能移动到下一行中的相邻节点（表示：下标与上一层节点下标相同，或等于上一层节点下标+1的两个节点）上

输入：
[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]
输出：11（即最小路径和为2+3+5+1=11	）

说明

1、用列表f记录所有路径的和
2、f的长度就是原列表的长度
3、其中f[0]的计算是非常直观n为len(list1)

for i in range(n):
	f[0] += list1[i][0]

4、list1中的第i行有i个元素（最后一个），

f[i]=f[i-1]+list1[i][i]

5、list1中的第i行中间的元素,即第j个元素，即0<j<i

f[j]=min(f[j],f[j-1])+list1[i][j] 
# [i][j]是i层倒数第二个元素
# f[j]是i-1层最后一个元素

方法一：

# -*- coding:UTF-8 -*-
class Solution:
	def minimumTotal(self,c):
		f=[0]*len(c)
		f[0]=c[0][0]
		for i in range(1,len(c)):
			f[i] = f[i-1]+c[i][i]
			for j in range(i-1,0,-1):
				f[j]=min(f[j],f[j-1])+c[i][j] 
			f[0] += c[i][0]
		return min(f)


c= [[2],[3,4],[6,5,9],[4,4,8,0]] #14	
result = Solution()
print(result.minimumTotal(c))

本文地址：https://blog.csdn.net/weixin_43579528/article/details/107358179