120.Triangle

题目描述

Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.

For example, given the following triangle

[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]
The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).

Note:

Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.

解题思路

开始做题之前，先把题目意思理清楚。题目中有几个关键字triangle和adjacent。首先是triangle，意为三角形，从它给出的输入就可以看见，这是一个金字塔型的图；然后是adjacent，意为临近，对于三角形一个点G[i][j]而言，它的邻接点有G[i+1][j]和G[i+1][j+1]。因此，这道题目的意思是：从根节点出发找到一条到最底部的路径，规定每次走它正下方的一个点或者右下方一个点，使这条路径的长度最短。

从上面的这两个约束条件我们不难发现，一共有 $2^n$ 条路径，n是金字塔的层数。如果我们要用搜索的方法找出所有的路径，那么我们就至少需要 $2^n$ 的额外空间，这个额外空间的消耗是指数级的，在n增大的时候，可能会出现爆炸性的增长，更何况题目要求我们只用O(n)的额外空间。

穷搜的方法行不通，我们试试用动归的思路。假设dp[i][j]表示，到达第i层第j个位置时需要的最小步数，那么很显然，它依赖于两个值——它正上方的点以及左上方的点。由此我们可以得到动归的状态转移方程:

triangle[i][j]代表三角形第i层第j个数
dp[i][j] = min(dp[i-1][j], dp[i-1][j-1]) + triangle[i][j];

这次我们的空间复杂度减少到 $O(n^2)$ ，也就是节点数目，这相较于之前的搜索已经好了很多。然而和题目要求还是有点距离。

因此，我们可以继续对它做优化。从之前背包问题的优化我们可以把二维的数组压缩成一维数组。考虑用dp[n]代替dp[n][n]。得到新的状态转移方程：

dp[j] = min(dp[j-1], dp[j])+triangle[i][j]

从这个方程我们可以看出，dp[j]依赖于前一个dp[j-1]，因此，循环迭代的顺序要反过来。这样，这道题基本就可以解决了。

时间复杂度分析

背包问题动态规划算法的复杂度O(n*n)

空间复杂度分析

与题目要求一致，O(n)

源码

class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        int layers = triangle.size(); 
        int dp[layers];
        for (int i = 0; i < layers; ++i) {
            dp[i] = 0;
        }
        dp[0] = triangle[0][0];
        for (int i = 1; i < layers; ++i) {
            dp[i] = dp[i-1] + triangle[i][i];
            for (int j = i-1; j > 0; --j) {
                dp[j] = min(dp[j], dp[j-1]) + triangle[i][j];
            }
            dp[0] = dp[0] + triangle[i][0];
        }
        int min = 999999;
        for (int i = 0; i < layers; ++i) {
            if (dp[i] < min) {
                min = dp[i];
            }
        }
        return min;
    }
};

120.Triangle（week10）