三角形的最小路径和(动态规划)[中等] - 《leetcode》

给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。

相邻的结点在这里指的是下标与上一层结点下标相同或者等于上一层结点下标 + 1 的两个结点。

例如，给定三角形：

[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]
自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。

说明：
如果你可以只使用 O(n) 的额外空间（n 为三角形的总行数）来解决这个问题，那么你的算法会很加分。

思路：每一步的局部最小值为全局最小值的基础，可以采用动态规划；
方法1：设置(size, size)大小的空间存储每一个点的从上往下的路径最小值和；同时考虑边界条件；

int minimumTotal(vector<vector<int>>& triangle) {
    int rows = triangle.size();
    if (rows == 0)
        return 0;
    // define state: min_path_dp[i][j]
    vector<vector<int>> min_path_dp(rows, vector<int>(rows, 0));
    for(int row = 0; row < rows; ++row){
        for(int col = 0; col <= row; ++col){
            if (row == 0)       // first row(border)
                min_path_dp[row][col] = triangle[row][col];
            else if (col == 0)  // first col(border)
                min_path_dp[row][col] = min_path_dp[row-1][col] + triangle[row][col];
            else if(col == row) // right border
                min_path_dp[row][col] = min_path_dp[row-1][col-1] + triangle[row][col];
            else                // other 
                min_path_dp[row][col] = min(min_path_dp[row-1][col-1], min_path_dp[row-1][col]) + triangle[row][col];
        }
    }
    int min_path_sum = INT_MAX;
    for(int i = 0; i < rows; ++i)
    {
        if (min_path_sum > min_path_dp[rows-1][i])
            min_path_sum = min_path_dp[rows-1][i];
    }
    return min_path_sum;
}
// time complexity: O(n^2)
// space complexity: O(n^2)

优化1：

方法1中有很多冗余的空间，可以优化，笔者在这里采用从下往上(从左往右)求(局部)最小路径和，最后的结果存在三角形顶点处；只需要一个O(n)的存储空间；

// ===================== optimize space complexity =========================
int minimumTotal(vector<vector<int>>& triangle) {
    int rows = triangle.size();
    if (rows == 0)
        return 0;
    if (rows == 1)
        return triangle[0][0];
    // define status: min_path_dp
    // status initialize and from down to up
    vector<int> min_path_dp = triangle[rows-1];

    for(int row = rows-2; row >= 0; --row){
        for(int col = 0; col <= row; ++col){
            min_path_dp[col] = min(min_path_dp[col], min_path_dp[col+1]) + triangle[row][col];
        }
    }
    // 第一个元素就是答案
    return min_path_dp[0];
}
// time complexity: O(n^2)
// space complexity: O(n)

优化2：

如果在面试的过程中，和面试官交流允许做inplace操作，则可以直接在原triangle上做dp;最后的三角形顶点就是最终的最小路径和。

// ===================== inplace operation =========================
int minimumTotal(vector<vector<int>>& triangle) {
    int rows = triangle.size();
    if (rows == 0)
        return 0;
    if (rows == 1)
        return triangle[0][0];
    // define state: min_path_dp
    // state initialize and from down to up
    // vector<int> min_path_dp = triangle[rows-1];


    // inplace operation from down to up and left to right
    for(int row = rows-2; row >= 0; --row){
        for(int col = 0; col <= row; ++col){
            triangle[row][col] = min(triangle[row+1][col], triangle[row+1][col+1]) + triangle[row][col];
        }
    }
    return triangle[0][0];
}
// time complexity: O(n^2)
// space complexity: O(1)

欢迎交流，批评指正！
WeChat Image_20200714101954.jpg