算法题--三角最小和

image.png

0. 链接

题目链接

1. 题目

Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.

For example, given the following triangle

[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]
The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).

Note:

Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.

2. 思路1: 带备忘录的递归

• 按TOP-DOWN的思路,

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

即每一个位置求极小值, 都先选中当前值, 再计算当前值确定的情况下，接下来的行内相邻列的极小值,

• 可以看到处于中间的元素, 都可能被两个父节点所选中, 因此存在重复计算的位置
• 为了减少计算量, 每个位置处已经计算过的极小值可以用备忘录存起来

memo_dict[(i, j)] = f(i, j)

• 最后返回f[0][0]即为目标值

• 时间复杂度: O(K^2)

• 空间复杂度: O(K^2)

3. 代码

# coding:utf8
from typing import List


class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        memo_dict = dict()

        def total_sum(i, j, triangle):
            if (i, j) in memo_dict:
                return memo_dict[(i, j)]
            rtn = triangle[i][j]
            if i == len(triangle) - 1:
                memo_dict[(i, j)] = rtn
                return memo_dict[(i, j)]
            else:
                memo_dict[(i, j)] = rtn + min(total_sum(i + 1, j, triangle),
                                              total_sum(i + 1, j + 1, triangle))
                return memo_dict[(i, j)]

        return total_sum(0, 0, triangle)


solution = Solution()
triangle = [
    [2],
    [3, 4],
    [6, 5, 7],
    [4, 1, 8, 3]
]
print('input: {}; output: {}'.format(triangle, solution.minimumTotal(triangle)))

输出结果

input: [[2], [3, 4], [6, 5, 7], [4, 1, 8, 3]]; output: 11

4. 结果

image.png

5. 思路2: 动态规划

按照BOTTOM-TOP的思路思考,要使得目标和最小,则最后一行的相邻两个元素所共用的父节点(处于倒数第二行), 必然会选中较小的那个子节点

[
     [2],   # 第0行
    [3,4],  # 第1行
   [6,5,7], # 第2行
  [4,1,8,3] # 第3行
]

注意第2行的6, 它必须要在第3行的4和1中选中1个，作为最终用来求和的元素, 那很容易可以得出, 它必然会选中min(4, 1) = 1, 从而得到6 + 1 = 7

同理, 第2行的5需要选择第3行的1或8, 则得到 5 + min(1, 8) = 6

所以, 可以看到, 所需要处理的元素数随行号变小而逐渐减小, 最多只需要O(N)的存储空间, N为最后一行的元素个数, 同时也为三角的行数

• 初始化

dp = triangle[-1].copy()

• 状态转移方程

对于i = n - 2 ~ 0, 第i行的第j列元素处
dp[j] = min(dp[j], dp[j + 1]) + triangle[i][j]

转移的示意图如下:

• 初始情况

   2
  3 4
 6 5 7
4 1 8 3

• 第1步

   2
  3 4
 7 6 10

• 第2步

   2
  9 10

• 第3步

11

• 时间复杂度: O(n^2)
• 空间复杂度: O(n)

6. 代码

# coding:utf8
from typing import List


class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        n = len(triangle)
        dp = triangle[n - 1].copy()
        for i in range(n - 2, -1, -1):
            for j in range(i + 1):
                dp[j] = min(dp[j], dp[j + 1]) + triangle[i][j]
        return dp[0]


solution = Solution()
triangle = [
    [2],
    [3, 4],
    [6, 5, 7],
    [4, 1, 8, 3]
]
print('input: {}; output: {}'.format(triangle, solution.minimumTotal(triangle)))

输出结果

input: [[2], [3, 4], [6, 5, 7], [4, 1, 8, 3]]; output: 11

7. 结果

image.png