题解 | 三角形最小路径和

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param triangle int整型二维数组 
# @return int整型
#

"""
 minTrace1(self , triangle: List[List[int]]) -> int:
这段代码的问题在于它使用了一种 "贪心" 策略来选择路径，这在很多情况下会得到错误的结果。
具体来说，代码的逻辑是：在每一步都选择当前行中相邻的两个元素中较小的那个。但这种局部最优的选择并不能保证最终得到全局最优解。
举个例子，对于输入 [[2],[3,4],[6,5,7],[4,1,8,3]]：
按照这段代码的逻辑，会选择 2 → 3 → 5 → 1，总和为 11（恰好是正确答案）
但如果我们修改一下数据，比如 [[2],[3,100],[100,5,7],[4,1,8,3]]
代码会选择 2 → 3 → 5 → 1，总和为 11
但实际上最优路径是 2 → 100 → 7 → 3，总和为 112，显然不对
问题的核心在于：
贪心算法只考虑当前步骤的最优选择，而不考虑未来可能的更优路径
三角形路径问题需要考虑所有可能的路径，才能找到真正的最小和
正确的做法应该使用动态规划，如之前展示的自底向上的方法，或者自顶向下的方法记录每个位置的最小路径和。

"""
class Solution:
    def minTrace(self , triangle: List[List[int]]) -> int:
        dp=[ row[:] for row in triangle  ]
        n =len(triangle)
        dp[0][0]=triangle[0][0]
        for  i in range(1,n):
            for j in range(0,i+1):
                if j ==0 : 
                    # 只能从上到下
                    dp[i][j]+=dp[i-1][j]
                elif j ==i:# 最后一列
                    dp[i][j]+=dp[i-1][j-1]
                else: 
                    dp[i][j]+=min(dp[i-1][j-1],dp[i-1][j])
        return min(dp[-1])


    # 贪心错误解法
    def minTrace1(self , triangle: List[List[int]]) -> int:
       # write code here
       res=triangle[0][0]
       n =len(triangle)
       #print(n)
       j=0
       if n<2:
        return res 
       for i in range(1,n):
            #print("tr",i,triangle[i])
            if j+1<len(triangle[i]):
                if triangle[i][j]>=triangle[i][j+1]:
                    res+=triangle[i][j+1 ]
                    #print("i ",i,res)
                    j+=1
                else:
                    res+=triangle[i][j]
                    #print("i2  ",i,res)
            else:
                res+=triangle[i][j]
                #print("i3  ",i,triangle[i][j])
       return res 

"""
    dp [i][j] 表示  坐标为i ,j 时候的和
    dp[i][j]=+  max(dp[i+1][j+1],dp[i][j+1])

"""