120. 三角形最小门路和

题目起源：力扣（LeetCode）https://leetcode-cn.com/problems/triangle

题目

给定一个三角形，找出自顶向下的最小门路和。每一步只能挪动到下一行中相邻的结点上。

相邻的结点 在这里指的是 下标 与 上一层结点下标 雷同或者等于 上一层结点下标 + 1 的两个结点。

例如，给定三角形：

[     [2],    [3,4],   [6,5,7],  [4,1,8,3]]

自顶向下的最小门路和为 11（即，2 + 3 + 5 + 1 = 11）。

解题思路

思路：递归，动静布局

首先先看题目中的提醒，【相邻的结点 在这里指的是 下标 与 上一层结点下标 雷同或者等于 上一层结点下标 + 1 的两个结点】。

咱们设 f(i, j) 为点 (i, j) 到底部的最小门路和。当初依据下面这个提醒，能够很容易失去公式：

f(i, j) = min(f(i+1, j), f(i+1, j+1)) + triangle[i][j]

也就是说，要求的门路和为：取以后结点相邻的两个结点最小值，加上以后结点的值。

递归

先尝试应用递归的办法求解，依据下面的公式，间接贴上代码：

class Solution:    def minimumTotal(self, triangle: List[List[int]]) -> int:        return self.path(triangle, 0, 0)        def path(self, triangle, i, j):        # 设置终止条件        if i == len(triangle):            return 0                # 间接应用公式        return min(self.path(triangle, i+1, j), self.path(triangle, i+1, j+1)) + triangle[i][j]

下面的代码执行超时，因为进行了大量的反复计算，当初思考进行优化。

递归（优化）

在这里，采纳建设备忘录的办法，防止反复的计算，同样这里贴上代码：

class Solution:    def minimumTotal(self, triangle: List[List[int]]) -> int:        # 备忘录        memo = {}                def path(triangle, i, j):            # 设置终止条件            if i == len(triangle):                return 0            if (i, j) in memo:                return memo[(i, j)]            memo[(i, j)] = min(path(triangle, i+1, j), path(triangle, i+1, j+1)) + triangle[i][j]            # 间接应用公式            return min(path(triangle, i+1, j), path(triangle, i+1, j+1)) + triangle[i][j]                return path(triangle, 0, 0)

下面的办法都是自顶向下的，当初咱们尝试应用动静布局，实现自底向上求解。

动静布局

应用动静布局的解法，先进行状态定义。

状态定义

设 dp[i][j] 为点 (i, j) 到底部的最小门路和。

状态转移方程

同样的，咱们依据最开始得出的公式，能够失去状态转移方程为：

dp[i][j] = min(dp[i+1][j], dp[i+1][j+1]) + triangle[i][j]

具体代码实现见【代码实现 # 动静布局】

动静布局（空间优化）

下面的动静布局算法中，咱们定义的是一个二维数组。当咱们计算 dp[i][j] 的时候，用到的是下一行的 dp[i+1][j] 和 dp[i+1][j+1]。那咱们能够间接思考从底部往上，定义一个一维数组。

具体代码实现见【代码实现 # 动静布局（空间优化）】

代码实现

# 动静布局class Solution:    def minimumTotal(self, triangle: List[List[int]]) -> int:        m = len(triangle)        dp = [[0] * (m+1) for _ in range(m+1)]        for i in range(m-1, -1, -1):            for j in range(0, i+1):                dp[i][j] = min(dp[i+1][j], dp[i+1][j+1]) + triangle[i][j]                return dp[0][0]# 动静布局（空间优化）class Solution:    def minimumTotal(self, triangle: List[List[int]]) -> int:        m = len(triangle)        dp = [0] * (m+1)        for i in range(m-1, -1, -1):            for j in range(0, i+1):                dp[j] = min(dp[j], dp[j+1]) + triangle[i][j]                return dp[0]

实现后果

动静布局（优化前）

欢送关注

公众号 【书所集录】