问题描述
题目：给定一个三角形， 每一步只能移动到下一行中相邻的结点上 ，求出自顶向下的最小路径和。
例如：
[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]
自顶向下的最小路径和为 11（即：2 + 3 + 5 + 1 = 11）。
解决方案
首先，这是一个一维动态规划问题，动态规划一般都是从下到上走。将dp数组初始化为‘三角形’最后一行的值，然后从倒数第二层开始向上，依次更改的dp数组中元素的个数，遍历到第几层就更改dp数组前面（那一层的长度）个。以问题描述中的例子为例：
初始化： [4,1,8,3]倒数第一层：[4,1,8,3]
第一次： [7,6,10,3]倒数第二层：[6,5,7]
第二次： [9,10,10,3]倒数第三层：[3,4]
第三次： [11,10,10,3]倒数第四层：[2]
计算过程很简单，以dp[i]表示由第i+1层到第i层的第i个元素的最小路径和，以j表示列数。dp[i]=下方与它相邻的两个值中的较小者的值+当前元素值，比如min(4,1)+6=7；min(1,8)+5=6；最后的dp[0]就是路径和的最小值。
这个计算式子也就是状态转移方程：dp[j] = min(dp[j], dp[j+1]) + triangle[i][j]
完整代码：
class Solution(object):def minimumTotal(triangle):# 获取triangle的长度，也就是‘三角形’的高n = len(triangle)# 初始化dp为‘三角形’最后那一行dp = triangle[-1]# 从下(倒数第二层)到上for i in range(n-2, -1, -1):# 更改dp前j个的值for j in range(i+1):dp[j] = min(dp[j], dp[j+1]) + triangle[i][j]# 返回dp第一个值return dp[0] |
|---|
结语
这是一道很简单的动态规划题目，主要思路就是找到状态转移函数。
动态规划其实存在一定的套路。 当求解的问题满足以下条件时，就应该使用动态规划： 主问题的可分解为很多的子问题（可以利用递归求解）并且递归求解时，很多子问题的答案会被多次重复利用。例如：斐波那契数列。
