题目

给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。

例如，给定三角形：

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

自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。

说明：

如果你可以只使用 O(n) 的额外空间（n 为三角形的总行数）来解决这个问题，那么你的算法会很加分。

分析

三角形具有树状结构，我们首先想到的是遍历算法，例如DFS。然而，如果你仔细观察，你会发现相邻的节点总是共享一个“分支”。换句话说，有重叠的子问题。此外，假设x和y是k的“子”，一旦从x和y到底部的最小路径已知，从k开始的最小路径可以在O(1)中确定，这是最佳子结构。下一次的结果会利用到上一次的结果。因此，就时间复杂性而言，动态规划将是这个问题的最佳解决方案。

自上而下 vs 自下而上

对于“自上而下”的动态规划，从最顶端的节点开始，我们递归地找到每个节点的最小路径和。计算路径和时，我们将其存储在数组中(记忆)；下次我们需要计算同一节点的路径和时，只需从数组中检索它。但是，您需要一个至少与输入三角形本身大小相同的缓存来存储 pathsum (占用 $O(N^2)$ 空间)。或许我们可以做一些剪枝优化，有可能释放一些在特定点之后永远不会使用的内存，但是在递归解决方案中不能直接看到正在处理的节点的顺序，因此决定丢弃缓存的哪一部分可能是一项困难的工作。

另一方面，自下而上的动态规划非常简单————我们从底层的节点开始；这些节点的最小路径和是节点本身的值。从那里开始，第 k 行第 i 节点处的最小路径总和将是其两个子节点的路径总和加上自身值中的较小者，即:

1
A[k][i] = Math.min( A[k+1][i], A[k+1][i+1]) + triangle[k][i];

或者更好的是，因为在计算 minpath[k] 之后，行 minpath[k+1] 将是无用的，所以我们可以简单地将 minpath 设置为一维数组，并随着迭代不断更新自身:

1
A[j] = Math.min(A[j], A[j+1]) + triangle.get(i).get(j);

动态规划小结

最近也做了不少关于动态规划的题目，之后还会不断进行补充，我觉得现在是一个不错的时机来对动态规划问题思路做一个总结：

拿到一道算法题，如何快速确定他可以用动态规划做呢？

首先，这道题需要求最优解，也就是说答案一般是唯一的，但是这个唯一是相对的，比如之前的机器人路径，明明最后有那么多条路径可以到终点，为什么也用动态规划呢？关于这个问题，我们要发散思维，虽然路径不是唯一的，但是可达路径数是唯一的。我们最终求的结果（返回值）也是路径数。所以我们采用动态规划，当然，还有下面一个重要原因。

在计算过程中，$n+1$ 步的计算可以用到第 $n$ 步的结果 ，我们可以建立一个存储结构来存放中间产生的结果，来给第 n+1 步提供便利，而不需要从第一步重新计算，这也是动态规划不同于回溯的地方。

代码

1
2
3
4
5
6
7
8
9
public int minimumTotal(List<List<Integer>> triangle) {
    int[] A = new int[triangle.size()+1];
    for(int i = triangle.size()-1; i >= 0; i--){
        for(int j = 0;j < triangle.get(i).size(); j++){
            A[j] = Math.min(A[j], A[j+1]) + triangle.get(i).get(j);
        }
    }
    return A[0];
}

更多动态规划问题

更多动态规划问题关注标签：动态规划