def maximumTotal(triangle): """ :type triangle: List[List[int]] :rtype: int """ dp = triangle #这边的初始化真的是牛逼,不仅不需要把把上面两行特殊的情况考虑进去,而且为下面也做了铺垫。因为是做累加,所以不需要初始化为0 m = len(dp) #dp是一个list列表,同样也可以看成是一个二维数组,如图所示 # [ [ # 8, [8], # 3,8 [3,8], # 8,1,0 [8,1,0], # 4,7,5,4 [4,7,5,4], # 3,5,2,6,5 [3,5,2,6,5] # ] ] # 可以知道3的下一行中相邻的结点为6和5,6的下一行中相邻的结点为4和1,5的下一行中相邻的结点为1和8 for i in range(1, m): for j in range(i+1): if j == 0: dp[i][j] += dp[i-1][j] #第一列的元素来源路径只可能是由上一行对应列的元素移动而来 if j> 0 and j == i: dp[i][j] += dp[i-1][j-1] elif (j > 0 and j < i): dp[i][j] += max(dp[i-1][j-1],dp[i-1][j]) #求两种移动路径的最大值 return (max(dp[m-1])) n = int(input()) traingle = [] for i in range(n): traingle.append(list(map(int,input().split()))) print(maximumTotal(traingle)) 代码很简单看懂
全部评论
(0) 回帖