LeetCode_Array_120. Triangle三角形最小路徑和（C++）【動态規劃】

目錄

​​1，題目描述​​

​​英文描述​​

​​中文描述​​

​​2，解題思路​​

​​3，AC代碼​​

​​4，解題過程​​

​​第一博​​

​​第二搏​​

1，題目描述

英文描述

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.

中文描述

給定一個三角形，找出自頂向下的最小路徑和。每一步隻能移動到下一行中相鄰的結點上。

相鄰的結點 在這裡指的是 下标 與 上一層結點下标 相同或者等于 上一層結點下标 + 1 的兩個結點。

例如，給定三角形：

[

     [2],

    [3,4],

   [6,5,7],

  [4,1,8,3]

]

自頂向下的最小路徑和為 11（即，2 + 3 + 5 + 1 = 11）。

來源：力扣（LeetCode）

連結：https://leetcode-cn.com/problems/triangle

著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

2，解題思路

從底向上，自左向右填充dp數組；

假設原始數組如下：

根據狀态轉移方程：dp[j] = min(dp[j], dp[j + 1]) + triangle[i][j]。

dp數組（一維，初始化為[0，0，0，0]）的整體疊代過程如下（空

以第一次疊代到第二次疊代的過程為例：

• 第一次疊代結束後dp數組為[4，1，8，3]，接着開始第二次疊代；
• dp[0] = min(dp[0], dp[1]) + triangle[3][0]，即7 = min(4，1) + 6。同理 6 = min(1，8) + 5，10
• 故第二次疊代結束後dp數組變為[7，6，10，3]（紅色即發生過變化的值）；

是以最終結果為dp[0]中的值；

3，AC代碼

class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        vector<int> dp(triangle.size() + 1);                    // dp數組大小初始化為末尾一行數組的大小 恰好等于triangle.size() + 1
        for(int i = triangle.size() - 1; i >= 0; --i) {
            for(int j = 0; j < triangle[i].size(); ++j) {
                dp[j] = min(dp[j], dp[j + 1]) + triangle[i][j];
            }
        }
        return dp[0];
    }
};      

4，解題過程

第一博

第一眼看上去，感覺應該使用遞歸來做，一頓操作下來

class Solution {
public:
    int ans = INT_MAX;
    void dfs(vector<vector<int>>& triangle, int depth, int index, int tem){
        if(depth == triangle.size()) {
            ans = min(ans, tem);
            return;
        }
        tem += triangle[depth][index];
        dfs(triangle, depth + 1, index, tem);
        dfs(triangle, depth + 1, index + 1, tem);
    }
    int minimumTotal(vector<vector<int>>& triangle) {
        dfs(triangle, 0, 0, 0);
        return ans;
    }
};      

果然逾時o(￣┰￣*)ゞ

第二搏

欣賞了大神的代碼，動态規劃，永遠滴神！