题目描述

给出一个三角形（数据数组），找出从上往下的最小路径和。每一步只能移动到下一行中的相邻结点上。

比如，给你如下三角形：

[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]

则从上至下最小路径和为 11（即，2 + 3 + 5 + 1 = 11）

注意：

加分项：如果你可以只使用 O(n) 的额外空间（n是三角形的行数）。

我的解法——DP（AC）

Matrix DP：我们可以发现如下规律，当我们求解minimumi时，我们会用到minimumi+1和minimumi+1，但是当求解完所有minimum[i]之后minimum[i+1]就没有用处了。
转移方程：
- S[i]/[j] = min(S[i+1]/[j] + S[i+1]/[j+1]) +S[i]/[j]
- 由于S[i]/[j]只与下一行的第j个元素和第j+1个元素相关，i的关系是固定的，因此我们可以省去这一维。开辟O(N)的数组，然后规划的时候使用S[j] = min(S[j+1], S[j]) +Triangle[i][j]就可以了。
有两种解决方案，自顶向下或者自底向上
复杂度O(n2)
结果：Beat44.37%
改进：在更新中间数组的时候注意。本题比较巧妙的地方在于，如果从上到下进行计算，更新中间数组比较麻烦，要用两个变量(下面第一种代码中pre 和cur)去记录当前的元素防止当前循环被更新后下一次循环就找不到了。如果从下到上进行计算，由于每行的大小在递减，所以正好可以直接在当前数组上进行更新。

class Solution:
    def minimumTotal(self, triangle):
        """
        :type triangle: List[List[int]]
        :rtype: int
        """
        
        m = len(triangle)
        n = len(triangle[m - 1]) if(m != 0) else 0
        dp = [0] * n
        
        if(m != 0 and n != 0):
            dp[0] = triangle[0][0]
        else:
            return 0
        
        for i in range(1,m):
            last = dp[0] # 记忆上一位防止被覆盖
            for j in range(i + 1):
                if(j == 0):
                    dp[j] = dp[j] + triangle[i][j]
                elif(j == i):
                    dp[j] = last + triangle[i][j]
                else:
                    templast = dp[j]
                    dp[j] = min(last,dp[j]) + triangle[i][j]
                    last = templast

        return min(dp)

参考答案

https://www.cnblogs.com/liujinhong/p/5551932.html