C++實(shí)現(xiàn)LeetCode(120.三角形)
[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.
這道題給了我們一個(gè)二維數(shù)組組成的三角形,讓我們尋找一條自上而下的路徑,使得路徑和最短。那么那道題后還是先考慮下暴力破解,我們可以發(fā)現(xiàn)如果要遍歷所有的路徑的話,那可以是階乘級(jí)的時(shí)間復(fù)雜度啊,OJ必滅之,趁早斷了念想比較好。必須要優(yōu)化時(shí)間復(fù)雜度啊,題目中給的例子很容易把人帶偏,讓人誤以為貪婪算法可以解題,因?yàn)榭搭}例子中的紅色數(shù)組,在根數(shù)字2的下方選小的數(shù)字3,在3的下方選小的數(shù)字5,在5的下方選小的數(shù)字1,每次只要選下一層相鄰的兩個(gè)數(shù)字中較小的一個(gè),似乎就能得到答案了。其實(shí)是不對(duì)的,貪婪算法可以帶到了局部最小,但不能保證每次都帶到全局最小,很有可能在其他的分支的底層的數(shù)字突然變的超級(jí)小,但是貪婪算法已經(jīng)將其他所有分支剪掉了。所以為了保證我們能得到全局最小,動(dòng)態(tài)規(guī)劃Dynamic Programming還是不二之選啊。其實(shí)這道題和 Dungeon Game 非常的類似,都是用DP來(lái)求解的問(wèn)題。那么其實(shí)我們可以不新建dp數(shù)組,而是直接復(fù)用triangle數(shù)組,我們希望一層一層的累加下來(lái),從而使得 triangle[i][j] 是從最頂層到 (i, j) 位置的最小路徑和,那么我們?nèi)绾蔚玫綘顟B(tài)轉(zhuǎn)移方程呢?其實(shí)也不難,因?yàn)槊總€(gè)結(jié)點(diǎn)能往下走的只有跟它相鄰的兩個(gè)數(shù)字,那么每個(gè)位置 (i, j) 也就只能從上層跟它相鄰的兩個(gè)位置過(guò)來(lái),也就是 (i-1, j-1) 和 (i-1, j) 這兩個(gè)位置,那么狀態(tài)轉(zhuǎn)移方程為:
triangle[i][j] = min(triangle[i - 1][j - 1], triangle[i - 1][j])
我們從第二行開(kāi)始更新,注意兩邊的數(shù)字直接賦值上一行的邊界值,那么最終我們只要在最底層找出值最小的數(shù)字,就是全局最小的路徑和啦,代碼如下:
解法一:
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()); } };
這種方法可以通過(guò)OJ,但是畢竟修改了原始數(shù)組triangle,并不是很理想的方法。在網(wǎng)上搜到一種更好的DP方法,這種方法復(fù)制了三角形最后一行,作為用來(lái)更新的一位數(shù)組。然后逐個(gè)遍歷這個(gè)DP數(shù)組,對(duì)于每個(gè)數(shù)字,和它之后的元素比較選擇較小的再加上面一行相鄰位置的元素做為新的元素,然后一層一層的向上掃描,整個(gè)過(guò)程和冒泡排序的原理差不多,最后最小的元素都冒到前面,第一個(gè)元素即為所求。代碼如下:
解法二:
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]; } };
下面我們來(lái)看一個(gè)例子,對(duì)于輸入數(shù)組:
-1
2 3
1 -1 -3
5 3 -1 2
下面我們來(lái)看DP數(shù)組的變換過(guò)程(紅色數(shù)字為每次dp數(shù)組中值改變的位置):
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.
到此這篇關(guān)于C++實(shí)現(xiàn)LeetCode(120.三角形)的文章就介紹到這了,更多相關(guān)C++實(shí)現(xiàn)三角形內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
- C++實(shí)現(xiàn)LeetCode(123.買股票的最佳時(shí)間之三)
- C++實(shí)現(xiàn)LeetCode(122.買股票的最佳時(shí)間之二)
- C++實(shí)現(xiàn)LeetCode(121.買賣股票的最佳時(shí)間)
- C++實(shí)現(xiàn)LeetCode(119.楊輝三角之二)
- C++實(shí)現(xiàn)LeetCode(118.楊輝三角)
- C++實(shí)現(xiàn)LeetCode(117.每個(gè)節(jié)點(diǎn)的右向指針之二)
- C++實(shí)現(xiàn)LeetCode(116.每個(gè)節(jié)點(diǎn)的右向指針)
- C++實(shí)現(xiàn)LeetCode(128.求最長(zhǎng)連續(xù)序列)
相關(guān)文章
如何使用visual studio2019創(chuàng)建簡(jiǎn)單的MFC窗口(使用C++)
這篇文章主要介紹了如何使用visual studio2019創(chuàng)建簡(jiǎn)單的MFC窗口(使用C++),文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2020-03-03C++利用Socket實(shí)現(xiàn)主機(jī)間的UDP/TCP通信
這篇文章主要為大家詳細(xì)介紹了C++如何利用Socket實(shí)現(xiàn)主機(jī)間的UDP/TCP通信功能,文中的示例代碼講解詳細(xì),感興趣的小伙伴可以了解一下2023-01-01利用C++實(shí)現(xiàn)通訊錄管理系統(tǒng)的完整代碼
通訊錄是一個(gè)可以記錄親人、好友信息的工具,下面這篇文章主要給大家介紹了關(guān)于利用C++實(shí)現(xiàn)通訊錄管理系統(tǒng)的相關(guān)資料,文中通過(guò)實(shí)例代碼介紹的非常詳細(xì),需要的朋友可以參考下2022-06-06C語(yǔ)言 完整游戲項(xiàng)目推箱子詳細(xì)代碼
經(jīng)典的推箱子是一個(gè)的古老游戲,目的是在訓(xùn)練你的邏輯思考能力。在一個(gè)狹小的倉(cāng)庫(kù)中,要求把木箱放到指定的位置,稍不小心就會(huì)出現(xiàn)箱子無(wú)法移動(dòng)或者通道被堵住的情況,所以需要巧妙的利用有限的空間和通道,合理安排移動(dòng)的次序和位置,才能順利的完成任務(wù)2021-11-11