本文共 2012 字，大约阅读时间需要 6 分钟。

链接：

大意：

给定一个三角形状的列表（具体看例子），要求找出一条从顶端到最底端路径，使路径上元素之和最小，返回最小的和。其中，每个上层节点只能到达其左下或者其右下节点。要求，尽量使用O(n)的空间复杂度，其中n为列表的行数。例子：

思路：

递归+动态规划。

首先，O(n)的空间复杂度，n为列表的行数。也就是使用dp数组时，只能开辟n长度的空间。另外找dp关系如下：

最终的dp[i]含义为：从顶点到底端第i节点最小路径的和。

在每一次递归中，都更新dp数组，意为从顶点到当前层的各个节点的最短路径和。

假设在第i层（顶点为第0层）的dp数组已求得（dp数组中有效元素个数为i + 1），那到了第i+1层时，记j为第i+1层节点的位置（j从0开始），记l为当前层的list，则对于j的取值可以分为以下三种情况：

j == 0 ：则 dp[j] = dp[j] + l.get(j)

j == l.size() - 1 ：也就是最后一个元素，只能由上一层的最后一个元素到达。则 dp[j] = dp[j - 1] + l.get(j)

j != 0 && j != l.size() - 1 ：也就是为中间元素。可以由上面的j - 1和j号元素到达。则 dp[j] = Math.min(dp[j], dp[j - 1]) + l.get(j)

注意：这里有一个小问题。就是假如 j == 1时，该层元素有两个，在计算了头号元素的dp值后，计算尾元素的dp值时使用的 dp[i - 1] 为最新的dp值了，所以需要使用一个临时数组tmp保存上一次dp的值。所以进行修改之后应该是如下：

j == 0 ：则 dp[j] = tmp[j] + l.get(j)

j == l.size() - 1 ：也就是最后一个元素，只能由上一层的最后一个元素到达。则 dp[j] = tmp[j - 1] + l.get(j)

j != 0 && j != l.size() - 1 ：也就是为中间元素。可以由上面的j - 1和j号元素到达。则 dp[j] = Math.min(tmp[j], tmp[j - 1]) + l.get(j)

代码：

class Solution {    public int minimumTotal(List
   
    
     > triangle) {        if (triangle.size() == 0)            return 0;        int[] dp = new int[triangle.size()];        dp[0] = triangle.get(0).get(0);        minimumTotal(triangle, 1, dp);        int min = Integer.MAX_VALUE;        for (int num : dp) {            if (num < min)                min = num;        }        return min;    }    public void minimumTotal(List
     
      
       > triangle, int h, int[] dp) {        if (h == triangle.size())            return ;        int[] tmp = new int[dp.length];        System.arraycopy(dp, 0, tmp, 0, dp.length); // 使用一个临时数组保存上一次dp的值        List
       
         l = triangle.get(h);        for (int i = 0; i < l.size(); i++) {            if (i == 0)                dp[i] = tmp[i] + l.get(i);            else if (i == l.size() - 1)                dp[i] = tmp[i - 1] + l.get(i);            else                 dp[i] = Math.min(tmp[i - 1], tmp[i]) + l.get(i);        }        minimumTotal(triangle, h + 1, dp);    }}
       
      
     
    
   

结果：

结论：

很有意思的一个题目，竟然把递归和动态规划结合了起来，算法设计也很有意思。 

转载地址：http://yxesi.baihongyu.com/