Triangle

LeetCode

第16天。

今天的题目是 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

1
2
3
4
5
6
[
     [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.

一道很常规的动态规划问题。

虽然例子中画出来的数组看起来很难确定路径，但是如果把它规整一下就可以得到：

1
2
3
4
2
3 4
6 5 7
4 1 8 3

因此对于位置(i,j)来说，到达它的路径一定经过上一层的(i-1, j)和(i-1,j-1)（注意其实triangle中必须保证0<=j<=i，那个位置才会有值)。

所以我们可以写出动态规划方程：

$$
dp[i, j]=min{dp[i-1, j], dp[i-1, j-1] } + triangle[i][j]
$$

其中dp[i,j]表示从顶端出发到达第i层第j个位置的最短路径的距离。其中dp[0,0]=triangle[0]以及dp[i,j]=INT_MAX,i<j，根据动态规划方程我们可以很容易的写出代码，同时为了使得空间复杂度为O(n)，我们可以只使用一个长度为n的数组来保存，之所以能做到是因为d[i, *]只依赖于d[i-1, *]，进一步的说，它只依赖于d[i-1, *-1]和d[i-1, *]，所以可以很容易改成一个用一个一维数组实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int minimumTotal(vector<vector<int>>& triangle) {
    int n = triangle.size();
    if (n == 0) return 0;
    vector<int> dp(n, INT_MAX);
    dp[0] = triangle[0][0];
    for(int i = 1;i < n;i++) {
        for(int j = i;j >= 0;j--) {
            dp[j] = min(dp[j], j>0?dp[j-1]:INT_MAX) + triangle[i][j];
            // cout << dp[j] << " ";
        }
        // cout << endl;
    }

    int res = INT_MAX;
    for(int i = 0;i < n;i++) res = min(res, dp[i]);
    return res;
}