# 第70期-基础算法：动态规划三角形最小路径和

Python是一门需要不断实践练习的编程语言，本文档将AI大学堂学员交流群的Python每周练习进行汇总，希望各位小伙伴能够多进行实践练习，逐渐爱上这门神奇的编程语言，掌握它并在生活中能够使用它。

# 1 问题描述

给定一个三角形 triangle ，找出自顶向下的最小路径和。

每一步只能移动到下一行中相邻的结点上。相邻的结点在这里指的是下标与上一层结点下标相同或者等于上一层结点下标 + 1 的两个结点。也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。

示例 1:

输入: triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
输出: 11
解释: 如下面简图所示： 2 3 4 6 5 7 4 1 8 3 自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。

示例 2:

输入: triangle = [[-10]]
输出: -10

初始代码

from typing import List
class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        #在此之间填写代码

print(Solution().minimumTotal([[2],[3,4],[6,5,7],[4,1,8,3]]))
print(Solution().minimumTotal( [[-10]]))

1
2
3
4
5
6
7

# 2 解题思路

标签：动态规划
我们用f[i][j]表示从三角形顶部走到位置(i, j)的最小路径和。这里的位置(i,j)指的是三角形中第i行第j列（均从0开始编号）的位置。
由于每一步只能移动到下一行「相邻的节点」上，因此要想走到位置 (i,j)，上一步就只能在位置 (i−1,j−1) 或者位置 (i - 1, j)(i−1,j)。我们在这两个位置中选择一个路径和较小的来进行转移，状态转移方程为：
f[i][j]=min(f[i−1][j−1],f[i−1][j])+c[i][j]
其中 c[i][j] 表示位置 (i,j) 对应的元素值。
注意三角形每一行两边的元素计算方法不同

# 3 解题方法

from typing import List
class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        a=len(triangle)
        def backtrack(triangle,n):
            for i in range(n+1):
                if i==0:
                    triangle[n][i]=triangle[n-1][i]+triangle[n][i]
                elif i==n:
                    triangle[n][i]=triangle[n-1][i-1]+triangle[n][i]
                else:
                    triangle[n][i]=min(triangle[n-1][i-1],triangle[n-1][i])+triangle[n][i]
            if n==a-1:return
            backtrack(triangle,n+1)
        if a>=2:backtrack(triangle,1)
        return min(triangle[-1])

print(Solution().minimumTotal([[2],[3,4],[6,5,7],[4,1,8,3]]))
print(Solution().minimumTotal( [[-10]]))

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

第1-3，18-19行： 题目中已经给出的信息，运行代码时要根据这些代码进行编辑
第4行： 定义变量a并赋值为三角形的行数
第5行： 创建backtrack函数用于每一行元素最小值计算，其中变量triangle为三角形，n为行数
第6行： for循环遍历三角形最后一行的每一个元素
第7-10行： 当该元素在三角形底边的两端时，计算其值就等于上一行对应位置的值加上本身值
第11-12行： 当该元素在三角形底边的中间时，计算其值就等于上一行对应位置左右元素的最小值加上本身值
第13行： 当该行计算完毕后，判断是否已经计算到三角形的最后一行，若是，结束递归
第14行： 若不是最后一行，则开始计算下一行的最大值
第15行： 若一共行数大于两行，引用函数开始计算
第16行： 当只有一行时，直接输出其中的唯一值代码运行结果为：

# 算法讲解

这里用到了基础算法：动态规划，简单讲解下这个算法：
动态规划
动态规划（Dynamic programming）是一种在数学、计算机科学和经济学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。动态规划常常适用于有重叠子问题和最优子结构性质的问题，动态规划方法所耗时间往往远少于朴素解法。动态规划背后的基本思想非常简单。大致上，若要解一个给定问题，我们需要解其不同部分（即子问题），再合并子问题的解以得出原问题的解。

性质

1. 最优子结构性质。如果问题的最优解所包含的子问题的解也是最优的，我们就称该问题具有最优子结构性质（即满足最优化原理）。最优子结构性质为动态规划算法解决问题提供了重要线索。

2. 子问题重叠性质。子问题重叠性质是指在用递归算法自顶向下对问题进行求解时，每次产生的子问题并不总是新问题，有些子问题会被重复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只计算一次，然后将其计算结果保存在一个表格中，当再次需要计算已经计算过的子问题时，只是在表格中简单地查看一下结果，从而获得较高的效率。

3. 无后效性：即某阶段状态一旦确定，就不受这个状态以后决策的影响。也就是说，某状态以后的过程不会影响以前的状态，只与当前状态有关。

性质

1. 划分：按照问题的特征，把问题分为若干阶段。注意：划分后的阶段一定是有序的或者可排序的

2. 确定状态和状态变量：将问题发展到各个阶段时所处的各种不同的客观情况表现出来。状态的选择要满足无后续性

3. 确定决策并写出状态转移方程：状态转移就是根据上一阶段的决策和状态来导出本阶段的状态。根据相邻两个阶段状态之间的联系来确定决策方法和状态转移方程

4. 边界条件：状态转移方程是一个递推式，因此需要找到递推终止的条件

# 4 视频解析

高清视频讲解，请查看AI大学堂Python基础实战100例 (opens new window)
关注『讯飞AI大学堂』公众号，发送 python100 即可领取Python基础实战100例源代码
AI大学堂公众号.png