問(wèn)題

給出一個(gè)三角形，找出從頂部至底部的最小路徑和。每一步你只能移動(dòng)到下一行的鄰接數(shù)字。

例如，給出如下三角形：

[

?? ? [2],

? ? [3,4],

?? [6,5,7],

? [4,1,8,3]

]

從頂部至底部的最小路徑和為11（即2+3+5+1=11）。

注意：

加分項(xiàng)－如果你能只使用O(n)的額外空間，n為三角形中的總行數(shù)。

?

初始思路

最直接的思路就是把路徑都走一遍。即從頂點(diǎn)出發(fā)，分別往左中右移動(dòng)（如果可能的話）；然后對(duì)走到的位置繼續(xù)進(jìn)行同樣移動(dòng)，直到走到最后一行。這樣就可以得到一個(gè)遞歸的方案，而遞歸的結(jié)束條件就是前面所說(shuō)的走到最后一行。偽代碼如下：

［最短路徑長(zhǎng)度］ 查找路徑(當(dāng)前節(jié)點(diǎn)坐標(biāo)，當(dāng)前路徑值)

如果是最后一行，返回當(dāng)前路徑值＋當(dāng)前節(jié)點(diǎn)值

否則

? 如果可以往左下走，左路徑 ＝?當(dāng)前路徑值 ＋?查找路徑(左下節(jié)點(diǎn)坐標(biāo)，當(dāng)前路徑值)

? 如果可以往下走，下路徑 ＝?當(dāng)前路徑值 ＋?查找路徑(下節(jié)點(diǎn)坐標(biāo)，當(dāng)前路徑值)

??如果可以往右下走，右路徑 ＝?當(dāng)前路徑值 ＋?查找路徑(右下節(jié)點(diǎn)坐標(biāo)，當(dāng)前路徑值)

? 找出左路徑，下路徑和右路徑中的最小值，返回該最小值

結(jié)合范例數(shù)據(jù)仔細(xì)分析一下上面的偽代碼， 可以發(fā)現(xiàn)其中有不少重復(fù)的步驟。如2->3->5和2->4->5后面的處理是完全相同的。回想一下我們?cè)?[LeetCode 132] - 回文分割I(lǐng)I(Palindrome Partitioning II)?中的做法，可以使用一個(gè)map保存已計(jì)算過(guò)的路徑來(lái)應(yīng)對(duì)這種重復(fù)。這里我們使用std::map<std::pair<int, int>, int>，將某點(diǎn)的坐標(biāo)作為map的key，從key出發(fā)的最小路徑作為值。

按以上思路完成代碼提交后發(fā)現(xiàn)有些測(cè)試用例不能通過(guò)，如：

[

? ? ? [-1]

? ? ?[3,2]

? ?[-3,1,-1]

]

按以上算法得出的值為-2，而期望的值為-1。-2為-1 -> 2-> -3這條路徑得出的值，而-1為路徑-1 -> 3 -> -3。看來(lái)題目中的鄰接（英文原文adjacent）規(guī)定只能往下或者右走。修改也很簡(jiǎn)單，將代碼中處理向左下走的那部分邏輯去掉即可。最終通過(guò)了Judge Small和Judge Large的代碼如下：

 1 class Solution {
 2     public:
 3         int minimumTotal(std::vector<std::vector<int> > &triangle)
 4         {
 5             pathInfo.clear();
 6             
 7             if(triangle.empty())
 8             {
 9                 return 0;
10             }
11 
12             return FindMinPath(triangle, 0, 0, 0);
13         }
14         
15     private:
16         int FindMinPath(std::vector<std::vector<int>>& input, int X, int Y, int currentPathValue)
17         {
18             if(X == input.size() - 1)
19             {
20                 return currentPathValue + input[X][Y];
21             }
22             
23             
24             auto iter = pathInfo.find(Coordinate(X, Y));
25             
26             if(iter != pathInfo.end())
27             {
28                 return currentPathValue + iter->second;
29             }
30             
31             
32             //int left = currentPathValue;
33             int down = currentPathValue;
34             int right = currentPathValue;
35             int min = 0;
36             bool minUpdated = false;
37             
38             /*
39             if(Y - 1 >= 0)
40             {
41                 left += FindMinPath(input, X + 1, Y - 1, input[X][Y]);
42                 min = left;
43                 minUpdated = true;
44             }
45             */
46             
47             if(Y < input[X + 1].size())
48             {
49                 down += FindMinPath(input, X + 1, Y, input[X][Y]);
50                 
51                 if(!minUpdated || min > down)
52                 {
53                     min = down;
54                     minUpdated = true;
55                 }
56                 
57                 if(Y + 1 < input[X + 1].size())
58                 {
59                     right += FindMinPath(input, X + 1, Y + 1, input[X][Y]);
60                     if(!minUpdated || min > right)
61                     {
62                         min = right;
63                     }
64                 }
65             }
66             
67                         pathInfo[Coordinate(X, Y)] = min - currentPathValue;
68             
69             return min;
70         }
71 
72         
73         std::map<std::pair<int, int>, int> pathInfo;
74         
75         typedef std::pair<int, int> Coordinate;
76     };

minimumTotal

?

獲得加分的方案

在上面的方案中，我們使用了以每個(gè)點(diǎn)坐標(biāo)為key的map來(lái)保存已計(jì)算過(guò)路徑，空間復(fù)雜度達(dá)到了n^2的級(jí)別，即不計(jì)map的額外消耗需要1 + 2 + 3 +..... + n = n(n-1) / 2的空間來(lái)儲(chǔ)存這些信息。

讓我們改變一下思路，不考慮某點(diǎn)出發(fā)的最短路徑，而考慮到達(dá)某點(diǎn)的最短路徑。給出一個(gè)點(diǎn)，怎么得到到該點(diǎn)的最短路徑？可以發(fā)現(xiàn)有三種情況：

• 該點(diǎn)為最左邊的點(diǎn)，即縱坐標(biāo)為0。由于我們前面已經(jīng)知道題目不允許往左下走，所以這種情況沒(méi)得選擇，最短路徑就是上面的點(diǎn)的最短路徑加當(dāng)前點(diǎn)的值。
• 該點(diǎn)為最右邊的點(diǎn)，即縱坐標(biāo)為n-1（n為該行的長(zhǎng)度）。由于是三角形，上一行中沒(méi)有縱坐標(biāo)為n-1的點(diǎn)。這種情況最短路徑只能是左上的點(diǎn)的最短路徑加當(dāng)前點(diǎn)的值。
• 其他情況。有兩種選擇，左上的點(diǎn)或者上方的點(diǎn)，需要取其中的小者來(lái)加當(dāng)前點(diǎn)的值。

用上面方法得出第n行的所有點(diǎn)的最短路徑后，我們發(fā)現(xiàn)第n-1行即上面一行的信息已經(jīng)不再需要被存儲(chǔ)了，因?yàn)榈趎+1行即下一行可以完全通過(guò)第n行的信息來(lái)算得自己的最短路徑值。那么我們需要的最大存儲(chǔ)空間就為最后一行的點(diǎn)的個(gè)數(shù)。不難看出，該數(shù)字和行數(shù)是相等的。這就符合了加分項(xiàng)中空間復(fù)雜度為O(n)的要求。

根據(jù)以上算法，我們將第一行中唯一一個(gè)值直接存到以縱坐標(biāo)為下標(biāo)的一個(gè)數(shù)組pathInfo中。然后從第二行開(kāi)始對(duì)每行中的每列進(jìn)行遍歷，不斷更新直到最后一行最后一列即可得到一個(gè)存有最后一行中每個(gè)點(diǎn)的最短路徑的數(shù)組。對(duì)數(shù)組pathInfo進(jìn)行一次遍歷找出最小值即為題目所求。在處理過(guò)程中，還需要注意一個(gè)小細(xì)節(jié)：遍歷每行時(shí)，需要從最右邊的列開(kāi)始。因?yàn)槿绻麖淖筮呴_(kāi)始，我們更新pathInfo[0]時(shí)就把上一層的信息覆蓋了，而新的pathInfo[1]還需要用到上一層的信息（它需要從上一層的0和1中選一個(gè)最小值）。

最終代碼如下：

 1 class Solution
 2     {
 3     public:
 4         int minimumTotal(std::vector<std::vector<int> > &triangle)
 5         {
 6             std::vector<int> pathInfo(triangle.size());
 7             
 8             pathInfo[0] = triangle[0][0];
 9             
10             for(int i = 1; i < triangle.size(); ++i)
11             {
12                 for(int j = i; j >= 0; --j)
13                 {
14                     if(j == 0)
15                     {
16                         pathInfo[j] = pathInfo[j] + triangle[i][j];
17                     }
18                     else if(j == triangle[i].size() - 1)
19                     {
20                         pathInfo[j] = pathInfo[j - 1] + triangle[i][j];
21                     }
22                     else
23                     {
24                         pathInfo[j] = pathInfo[j] < pathInfo[j - 1] ? pathInfo[j] : pathInfo[j - 1];
25                         pathInfo[j] += triangle[i][j];
26                     }
27                 }
28             }
29             
30             int min = *pathInfo.begin();
31             for(auto iter = pathInfo.begin() + 1; iter != pathInfo.end(); ++iter)
32             {
33                 if(min > *iter)
34                 {
35                     min = *iter;
36                 }
37             }
38             
39             return min;
40         }
41     };

minimumTotal_Bonus

使用了新的算法后，不但減少了空間復(fù)雜度，遞歸也不再需要了，過(guò)Judge Large的時(shí)間由130ms左右降到了40ms左右。

?

轉(zhuǎn)載于:https://www.cnblogs.com/shawnhue/p/leetcode_120.html

總結(jié)

以上是生活随笔為你收集整理的[LeetCode 120] - 三角形(Triangle)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。