解题思路:
动态规划
注意:从山上往山下走时,只能往下走或则往右下走。
①用数组A存放藏宝图,A[i][j]表示第i行第j列的珠宝数量
②建立一个大小为(n+1)*(n+1)的二维数组dp,初始化为0。dp[i][j]表示从上往下走到第i行第j列时所拥有的最大珠宝数量。
③令dp[1][1] = A[1][1],更新dp数组
④找出最大值ans = max(dp[n])
注意事项:
参考代码:
def f(n): A = [None] for i in range(n): #藏宝图 temp = [None] + [int(i) for i in input().strip().split()] A.append(temp) dp = [[0 for j in range(n+1)] for i in range(n+1)] dp[1][1] = A[1][1] for i in range(2,n+1): #更新dp数组 for j in range(1,i+1): dp[i][j] = max(dp[i-1][j]+A[i][j],dp[i-1][j-1]+A[i][j]) ans = max(dp[n]) #找出最大值 print(ans) if __name__ == '__main__': n = int(input()) f(n)
0.0分
1 人评分