欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

荐 LeetCode 120. 三角形最小路径和 | Python

程序员文章站 2022-12-21 08:31:27
使用动态规划,递归的思路,解决 LeetCode 《120. 三角形最小路径和》问题...

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]

实现结果


动态规划(优化前)
荐
                                                        LeetCode 120. 三角形最小路径和 | Python

荐
                                                        LeetCode 120. 三角形最小路径和 | Python

欢迎关注


公众号 【书所集录

本文地址:https://blog.csdn.net/weixin_45642918/article/details/107342643