一、題目描述

給定一個(gè)三角形 triangle ，找出自頂向下的最小路徑和。

每一步只能移動(dòng)到下一行中相鄰的結(jié)點(diǎn)上。相鄰的結(jié)點(diǎn) 在這里指的是 下標(biāo) 與 上一層結(jié)點(diǎn)下標(biāo) 相同或者等于 上一層結(jié)點(diǎn)下標(biāo) + 1 的兩個(gè)結(jié)點(diǎn)。也就是說，如果正位于當(dāng)前行的下標(biāo) i ，那么下一步可以移動(dòng)到下一行的下標(biāo) i 或 i + 1 。

示例 1

輸入：triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
輸出：11
解釋：如下面簡(jiǎn)圖所示：
   2
  3 4
 6 5 7
4 1 8 3
自頂向下的最小路徑和為 11（即，2 + 3 + 5 + 1 = 11）。

示例 2

輸入：triangle = [[-10]]
輸出：-10

提示：
1 <= triangle.length <= 200
triangle[0].length == 1
triangle[i].length == triangle[i - 1].length + 1
-10^4 <= triangle[i][j] <= 10^4

二、代碼

代碼如下：

class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        for row in range(1,len(triangle)):
            print(f"row = {row} 時(shí)，當(dāng)前行的長(zhǎng)度為：",len(triangle[row]))
            for col in range(len(triangle[row])):
                if col > 0 and col < len(triangle[row])-1 : #當(dāng)前位置非邊界處，有2種情況
                    path = [e+triangle[row][col] for e in triangle[row-1][col-1:col+1]]
                if col == 0: #當(dāng)前位置在當(dāng)前行最左邊 ， 只有一種情況
                    path = [triangle[row-1][col] + triangle[row][col]]
                if col == len(triangle[row])-1 :#當(dāng)前位置在當(dāng)前行最右邊 ， 只有一種情況
                    path = [triangle[row - 1][-1] + triangle[row][col]]
                print("path:",path)
                # 在path中選擇最小的一個(gè)值，作為當(dāng)前位置的值
                triangle[row][col] = min(path)

        print(triangle)
        print(min(triangle[-1]))
        return  min(triangle[-1])

三、解題思路

本題是尋找自頂向下三角形最小路徑和，其規(guī)則類似于二叉樹，當(dāng)前節(jié)點(diǎn)只能由其相鄰的父結(jié)點(diǎn)下來。
本題解最容易想到的思路是把所有路徑都遍歷一遍的方法，即采用回溯方法把每一條可能的路徑都計(jì)算出總和，最后選擇最小值返回即可。但是該方法的問題是，并不能滿足輸入序列非常大的時(shí)候，并且回溯方法耗費(fèi)時(shí)間，容易導(dǎo)致“超出時(shí)間限制”的問題。
故本題解尋求該三角形數(shù)組的規(guī)律，具體思路是計(jì)算每層中每一個(gè)元素對(duì)應(yīng)的最小路徑總和，然后層層遞進(jìn)，直到計(jì)算到三角形最后一層結(jié)束。最終所需要尋求的結(jié)果從三角形最后一層中找到最小值即可。
以triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]為例：

									   2
									  3 4
									 6 5 7
									4 1 8 3

我們從三角形第二層（即row = 1）開始計(jì)算，計(jì)算該層每一個(gè)元素當(dāng)前對(duì)應(yīng)的最短路徑總和，因?yàn)榈诙又忻恳粋€(gè)元素只可能從第一層中唯一一個(gè)元素走下來，所以當(dāng)前層每一個(gè)元素對(duì)應(yīng)的最短路徑和應(yīng)該為：[3, 4]->[3+2, 4+2]->[5, 6]，用[5, 6]替換原本的數(shù)據(jù)，用于第三層的計(jì)算。

								     2
								  3+2 4+2
								 6   5   7
							   4   1   8   3

然后計(jì)算第三層每一個(gè)元素對(duì)應(yīng)的最短路徑總和，這里出現(xiàn)了新情況，就是有元素（位于中間位置的5）存在不同路徑的總和（即[5+5 or 6+5]->[10 or 11]），此時(shí)我們秉承著找最小路徑的原則，選擇最小的值（即從左邊下來的路徑5+5，求得10）來作為當(dāng)前的位置的最小路徑和。最后得到[11, 10, 13]，用與第四層的計(jì)算。

								       2
								   5       6
								 6+5   5+5   7+6
							   4     1     8     3

同理，最后一層中的計(jì)算方法也同第三層一樣，在第四層中，存在有多個(gè)（1和8）不同路徑的元素點(diǎn)，我們還是取其對(duì)應(yīng)最小值即可，最后結(jié)果為[15, 11, 18, 16]:

							            2
							       5          6
							 11          10       13
						   4+11     1+10     8+10     3+13

我們所需要求的結(jié)果，就是最后一層中的最小值，即11，返回即可。
以上便是尋求規(guī)律所得題解。文章來源地址http://www.zghlxwxcb.cn/news/detail-421420.html

到了這里，關(guān)于120. 三角形最小路徑和 Python的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！