题解 | 三角形取数(Hard Version)

inp=input().split(' ')
n,k=int(inp[0]),int(inp[1])

num_mat=[]
all_num=[]
for i in range(n):
    tar=input().split(' ')
    target=[int(x) for x in tar]
    num_mat.append(target)
    all_num.append([float('-inf')]*len(target))

# 从最下面一行往第一行迭代相加找到全局最优解，k只会限制最后一行的位置
# 而每一行(i,1)会对应上一行的(i-1,0)
for i in range(n):
    for j in range(2*(n-i)-1):
        if i >0:
            all_num[n-1-i][j]=max(all_num[n-i][j],all_num[n-i][j+1],all_num[n-i][j+2])+num_mat[n-1-i][j]
        else:
            if k>=n-1:
                all_num[n-1-i][j]=num_mat[n-1-i][j]
            else:
                for numb in range(n-k-1,n+k):
                    all_num[n-1-i][numb]=num_mat[n-1-i][numb]

print(all_num[0][0])