题目链接：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.

这道题的要求是给定一个三角形，找到从上到下和最小的路径。每一步可能移动到下面行的相邻数字。

动态规划，找从上到下的最小路径，可以采用数组来存储到达某一行的所有位置的最短路径，最后在从中找出最小的即可。递推公式如下：

  • 当为该行最后一个元素的时候，dp[i] = dp[i - 1] + triangle[i][i];
  • 当为该行第一个元素的时候，dp[0] = dp[0] + triangle[i][0];
  • 其他情况，dp[j] = min(dp[j - 1], dp[j]) + triangle[i][j]。

时间复杂度：O(n2)

空间复杂度：O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

class Solution
{
public:
    int minimumTotal(vector<vector<int> > &triangle)
    {
        int n = triangle.size();
        vector<int> vi(n, 0); // 存储最小路径
        for(int i = 0; i < n; ++ i)
        {
            if(i > 0) // 不是第0行的情况，处理最后一个元素
                vi[i] = vi[i - 1] + triangle[i][i];
            for(int j = i - 1; j > 0; -- j)
                vi[j] = min(vi[j - 1], vi[j]) + triangle[i][j];
            vi[0] += triangle[i][0]; // 第一个元素
        }
        return *min_element(vi.begin(), vi.end());
    }
};