python-数字三角形

解题思路:

参考博客https://www.jianshu.com/p/99e379de3368

动态规划。

建立一个大小为（n+1）*（n+1）二维数组dp,其中dp[i][j]为从顶点走到到第i行第j列的位置路径和。

建立一个大小为（n+1）*（n+1）二维数组time,其中time[i][j]为从顶点走到到第i行第j列的位置处往右下的次数与往左下的次数的差值。（这里规定，每往右下一次time[i][j]+1，往左下一次time[i][j]-1)

到最后一行时，只有-1<=time[n-1][i] <=1的dp[n-1][i]为符合条件的值，从中选取最大值即可。

注意事项:

参考代码:

n = int(input())  
  
A = []  
for i in range(n):         #存放三角形
    A = A + [[0] + [int(i) for i in input().strip().split()]+[0]]  
  
dp = [[0 for j in range(n+1)] for i in range(n+1)]     #存放从顶点到某一位置处的和
time = [[0 for j in range(n+1)] for i in range(n+1)]   #存放从顶点到某一位置的往右下的次数与往左下的次数的差值
  
dp[0][1] = A[0][1]    #初始化动态数组
for i in range(1,n):  
    for j in range(1,i+2):  
        if dp[i-1][j-1] > dp[i-1][j]:  #往右下
            dp[i][j] = dp[i-1][j-1] + A[i][j]  
            time[i][j] = time[i-1][j-1]+1  
        else:                          #往左下
            dp[i][j] = dp[i-1][j] + A[i][j]  
            time[i][j] = time[i-1][j]-1  
  
maxnum = 0  
for i in range(1,n+1):  
    if -1<=time[n-1][i]<=1 and dp[n-1][i] > maxnum:  
        maxnum = dp[n-1][i]  
          
print(maxnum)