給定一個(gè)三角形，找出自頂向下的最小路徑和。每一步只能移動(dòng)到下一行中相鄰的結(jié)點(diǎn)上。

10年積累的網(wǎng)站建設(shè)、成都網(wǎng)站設(shè)計(jì)經(jīng)驗(yàn)，可以快速應(yīng)對客戶對網(wǎng)站的新想法和需求。提供各種問題對應(yīng)的解決方案。讓選擇我們的客戶得到更好、更有力的網(wǎng)絡(luò)服務(wù)。我雖然不認(rèn)識你，你也不認(rèn)識我。但先制作網(wǎng)站后付款的網(wǎng)站建設(shè)流程，更有南靖免費(fèi)網(wǎng)站建設(shè)讓你可以放心的選擇與我們合作。

例如，給定三角形：

[

     [2],

    [3,4],

   [6,5,7],

  [4,1,8,3]

]

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

說明：

如果你可以只使用 O(n) 的額外空間（n 為三角形的總行數(shù)）來解決這個(gè)問題，那么你的算法會(huì)很加分。

//使用一個(gè)一位數(shù)組，長度為最后一條邊的長度
class Solution {
    public:    
        int minimumTotal(vector<vector<int>>& triangle) {
            int rows = triangle.size();
            if(rows == 0){            
                return 0;
            }        
            int columns = triangle[rows - 1].size();
            vector<int> dp(columns, 0);
            dp[0] = triangle[0][0];        
            for(int i = 1; i< rows; i++){
                for(int j = triangle[i].size() - 1; j >= 0; j--){                
                    if(j == triangle[i].size() - 1){
                        dp[j] = dp[j - 1] + triangle[i][j];
                    }else if(j == 0){
                        dp[j] = dp[j] + triangle[i][j];
                    }else{
                        dp[j] = std::min(dp[j - 1], dp[j]) + triangle[i][j];
                    }
                }            
                for(int i = 0; i< columns; i++){
                    cout<< dp[i];
                }
                cout<< endl;
            }
            sort(dp.begin(), dp.end());        
            return dp[0];
        }
};

名稱欄目：三角形最小路徑和
文章源于：http://www.rwnh.cn/article36/psggsg.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供軟件開發(fā)、微信小程序、定制開發(fā)、標(biāo)簽優(yōu)化、面包屑導(dǎo)航、商城網(wǎng)站

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)