Dynamic Programming - 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).

这题要求我们求出一个三角形中从顶到底最小路径和，并且要求只能使用O(n)的空间。

这题有两种解法，自顶向下以及自底向上。

首先来看自顶向下，根据题目我们知道，每向下一层，我们只能选择邻接数字进行累加，譬如上面第1行的数字3，它的下一行邻接数字就是6和5。

我们假设dp[m][n]保存了第m行第n个节点的最小路径和，我们有如下dp方程

• dp[m + 1][n] = min(dp[m][n], dp[m][n - 1]) + triangle[m + 1][n] if n > 0
• dp[m + 1][0] = dp[m][0] + triangle[m + 1][0]

因为只能使用O(n)的空间，所以我们需要滚动计算，使用一个一位数组保存每层的最小路径和，参考Pascal’s Triangle，我们知道，为了防止计算的时候不覆盖以前的值，所以我们需要从后往前计算。

代码如下

class Solution {
public:
    int minimumTotal(vector<vector<int> > &triangle) {
        int row = triangle.size();
        if(row == 0) {
            return 0;
        }
        //初始化为最大值
        vector<int> total(row, INT_MAX);
        total[0] = triangle[0][0];
        int minTotal = INT_MAX;
        for(int i = 1; i < row; i++) {
            for(int j = i; j >= 0; j--) {
                if(j == 0) {
                    total[j] = total[j] + triangle[i][j];
                } else {
                    //上一层total[i]为INT_MAX，不会影响最小值
                    total[j] = min(total[j - 1], total[j]) + triangle[i][j];
                }
            }
        }
        for(int i = 0; i < row; i++) {
            minTotal = min(minTotal, total[i]);
        }
        return minTotal;
    }
};

区别于自顶向下，另一种更简单的做法就是自底向上了。dp方程为

dp[m][n] = min(dp[m + 1][n], dp[m + 1][n + 1]) + triangle[m][n]

我们仍然可以使用一位数组滚动计算。

代码如下

class Solution {
public:
    int minimumTotal(vector<vector<int> > &triangle) {
        if(triangle.empty()) {
            return 0;
        }
        int row = triangle.size();
        vector<int> dp;
        dp.resize(row);
        //用最底层的数据初始化
        for(int i = 0; i < dp.size(); i++) {
            dp[i] = triangle[row-1][i];
        }
        for(int i = row - 2; i >= 0; i--) {
            for(int j = 0; j <= i; j++) {
                dp[j] = triangle[i][j] + min(dp[j], dp[j + 1]);
            }
        }
        return dp[0];
    }
};