建站
咨詢
售后
建站咨詢
新聞中心
本篇內容介紹了“C++怎么實現(xiàn)三角形”的有關知識，在實際案例的操作過程中，不少人都會遇到這樣的困境，接下來就讓小編帶領大家學習一下如何處理這些情況吧！希望大家仔細閱讀，能夠學有所成！
十余年的新昌網(wǎng)站建設經(jīng)驗，針對設計、前端、開發(fā)、售后、文案、推廣等六對一服務，響應快，48小時及時工作處理。網(wǎng)絡營銷推廣的優(yōu)勢是能夠根據(jù)用戶設備顯示端的尺寸不同，自動調整新昌建站的顯示方式，使網(wǎng)站能夠適用不同顯示終端，在瀏覽器中調整網(wǎng)站的寬度，無論在任何一種瀏覽器上瀏覽網(wǎng)站，都能展現(xiàn)優(yōu)雅布局與設計，從而大程度地提升瀏覽體驗。創(chuàng)新互聯(lián)從事“新昌網(wǎng)站設計”,“新昌網(wǎng)站推廣”以來，每個客戶項目都認真落實執(zhí)行。
三角形
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.
這道題給了我們一個二維數(shù)組組成的三角形，讓我們尋找一條自上而下的路徑，使得路徑和最短。那么那道題后還是先考慮下暴力破解，我們可以發(fā)現(xiàn)如果要遍歷所有的路徑的話，那可以是階乘級的時間復雜度啊，OJ必滅之，趁早斷了念想比較好。必須要優(yōu)化時間復雜度啊，題目中給的例子很容易把人帶偏，讓人誤以為貪婪算法可以解題，因為看題例子中的紅色數(shù)組，在根數(shù)字2的下方選小的數(shù)字3，在3的下方選小的數(shù)字5，在5的下方選小的數(shù)字1，每次只要選下一層相鄰的兩個數(shù)字中較小的一個，似乎就能得到答案了。其實是不對的，貪婪算法可以帶到了局部最小，但不能保證每次都帶到全局最小，很有可能在其他的分支的底層的數(shù)字突然變的超級小，但是貪婪算法已經(jīng)將其他所有分支剪掉了。所以為了保證我們能得到全局最小，動態(tài)規(guī)劃Dynamic Programming還是不二之選啊。其實這道題和 Dungeon Game 非常的類似，都是用DP來求解的問題。那么其實我們可以不新建dp數(shù)組，而是直接復用triangle數(shù)組，我們希望一層一層的累加下來，從而使得 triangle[i][j] 是從最頂層到 (i, j) 位置的最小路徑和，那么我們如何得到狀態(tài)轉移方程呢？其實也不難，因為每個結點能往下走的只有跟它相鄰的兩個數(shù)字，那么每個位置 (i, j) 也就只能從上層跟它相鄰的兩個位置過來，也就是 (i-1, j-1) 和 (i-1, j) 這兩個位置，那么狀態(tài)轉移方程為：
triangle[i][j] = min(triangle[i - 1][j - 1], triangle[i - 1][j])
我們從第二行開始更新，注意兩邊的數(shù)字直接賦值上一行的邊界值，那么最終我們只要在最底層找出值最小的數(shù)字，就是全局最小的路徑和啦，代碼如下：
解法一：
class Solution {
public:
int minimumTotal(vector>& 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，但是畢竟修改了原始數(shù)組triangle，并不是很理想的方法。在網(wǎng)上搜到一種更好的DP方法，這種方法復制了三角形最后一行，作為用來更新的一位數(shù)組。然后逐個遍歷這個DP數(shù)組，對于每個數(shù)字，和它之后的元素比較選擇較小的再加上面一行相鄰位置的元素做為新的元素，然后一層一層的向上掃描，整個過程和冒泡排序的原理差不多，最后最小的元素都冒到前面，第一個元素即為所求。代碼如下：
解法二：
class Solution {
public:
int minimumTotal(vector>& triangle) {
vector 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];
}
}; 下面我們來看一個例子，對于輸入數(shù)組：
-1
2 3
1 -1 -3
5 3 -1 2
下面我們來看DP數(shù)組的變換過程（紅色數(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
“C++怎么實現(xiàn)三角形”的內容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業(yè)相關的知識可以關注創(chuàng)新互聯(lián)網(wǎng)站，小編將為大家輸出更多高質量的實用文章！
網(wǎng)站題目：C++怎么實現(xiàn)三角形
鏈接分享：http://fisionsoft.com.cn/article/iedsgg.html
