python-夺宝奇兵

解题思路:
动态规划

注意：从山上往山下走时，只能往下走或则往右下走。

①用数组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)