本文讲述了python基础编程100例：第70期-基础算法：动态规划 三角形最小路径和！具有很好的参考价值，希望对大家有所帮助。一起跟随六星小编过来看看吧，具体如下:

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

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]]))

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-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. 边界条件：状态转移方程是一个递推式，因此需要找到递推终止的条件

更多相关技术内容咨询欢迎前往并持续关注六星社区了解详情。

想高效系统的学习Python编程语言，推荐大家关注一个微信公众号：Python编程学习圈。每天分享行业资讯、技术干货供大家阅读，关注即可免费领取整套Python入门到进阶的学习资料以及教程，感兴趣的小伙伴赶紧行动起来吧。