动态规划--三角形最小路径和

问题描述

给定一个三角形 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

代码

class Solution(object):def minimumTotal(self, triangle):""":type triangle: List[List[int]]:rtype: int"""min_sum = []for i in range(len(triangle)):sum_i_min = []if i == 0:sum_i_min.append(triangle[i][0])else:for j in range(len(triangle[i])):if j == 0:print(sum_i_min)sum_i_min.append(triangle[i][j] + min_sum[i-1][j])elif j == len(triangle[i]) - 1:sum_i_min.append(triangle[i][j] + min_sum[i-1][j-1])else:sum_i_min.append(min(triangle[i][j] + min_sum[i-1][j-1], triangle[i][j] + min_sum[i-1][j]))min_sum.append(sum_i_min)return min(min_sum[-1])