C++實現LeetCode(120.三角形)

Posted on by

[LeetCode] 120.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.

這道題給瞭我們一個二維數組組成的三角形，讓我們尋找一條自上而下的路徑，使得路徑和最短。那麼那道題後還是先考慮下暴力破解，我們可以發現如果要遍歷所有的路徑的話，那可以是階乘級的時間復雜度啊，OJ必滅之，趁早斷瞭念想比較好。必須要優化時間復雜度啊，題目中給的例子很容易把人帶偏，讓人誤以為貪婪算法可以解題，因為看題例子中的紅色數組，在根數字2的下方選小的數字3，在3的下方選小的數字5，在5的下方選小的數字1，每次隻要選下一層相鄰的兩個數字中較小的一個，似乎就能得到答案瞭。其實是不對的，貪婪算法可以帶到瞭局部最小，但不能保證每次都帶到全局最小，很有可能在其他的分支的底層的數字突然變的超級小，但是貪婪算法已經將其他所有分支剪掉瞭。所以為瞭保證我們能得到全局最小，動態規劃Dynamic Programming還是不二之選啊。其實這道題和 Dungeon Game 非常的類似，都是用DP來求解的問題。那麼其實我們可以不新建dp數組，而是直接復用triangle數組，我們希望一層一層的累加下來，從而使得 triangle[i][j] 是從最頂層到 (i, j) 位置的最小路徑和，那麼我們如何得到狀態轉移方程呢？其實也不難，因為每個結點能往下走的隻有跟它相鄰的兩個數字，那麼每個位置 (i, j) 也就隻能從上層跟它相鄰的兩個位置過來，也就是 (i-1, j-1) 和 (i-1, j) 這兩個位置，那麼狀態轉移方程為：

triangle[i][j] = min(triangle[i – 1][j – 1], triangle[i – 1][j])

我們從第二行開始更新，註意兩邊的數字直接賦值上一行的邊界值，那麼最終我們隻要在最底層找出值最小的數字，就是全局最小的路徑和啦，代碼如下：

解法一：

class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        for (int i = 1; i < triangle.size(); ++i) {
            for (int j = 0; j < triangle[i].size(); ++j) {
                if (j == 0) {
                    triangle[i][j] += triangle[i - 1][j];
                } else if (j == triangle[i].size() - 1) {
                    triangle[i][j] += triangle[i - 1][j - 1];
                } else {
                    triangle[i][j] += min(triangle[i - 1][j - 1], triangle[i - 1][j]);
                }
            }
        }
        return *min_element(triangle.back().begin(), triangle.back().end());
    }
};

這種方法可以通過OJ，但是畢竟修改瞭原始數組triangle，並不是很理想的方法。在網上搜到一種更好的DP方法，這種方法復制瞭三角形最後一行，作為用來更新的一位數組。然後逐個遍歷這個DP數組，對於每個數字，和它之後的元素比較選擇較小的再加上面一行相鄰位置的元素做為新的元素，然後一層一層的向上掃描，整個過程和冒泡排序的原理差不多，最後最小的元素都冒到前面，第一個元素即為所求。代碼如下：

解法二： 

class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        vector<int> dp(triangle.back());
        for (int i = (int)triangle.size() - 2; i >= 0; --i) {
            for (int j = 0; j <= i; ++j) {
                dp[j] = min(dp[j], dp[j + 1]) + triangle[i][j];
            }
        }
        return dp[0];
    }
};

下面我們來看一個例子，對於輸入數組：

     -1

    2   3

  1  -1  -3

5   3   -1   2

下面我們來看DP數組的變換過程（紅色數字為每次dp數組中值改變的位置）：

DP：5  3  -1  2

DP：4  3  -1  2

DP：4  -2  -1  2

DP：4  -2  -4  2

DP：0  -2  -4  2

DP：0  -1  -4  2

DP：-2  -1  -4  2

參考資料：

https://leetcode.com/problems/triangle/

https://leetcode.com/problems/triangle/discuss/38730/DP-Solution-for-Triangle

https://leetcode.com/problems/triangle/discuss/38918/C%2B%2B-top-down-and-bottom-up-solutions.

到此這篇關於C++實現LeetCode(120.三角形)的文章就介紹到這瞭,更多相關C++實現三角形內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！

推薦閱讀：