解题思路:
动态规划
注意:从山上往山下走时,只能往下走或则往右下走。
①用数组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 人评分
2003年秋浙江省计算机等级考试二级C 编程题(2) (C语言代码)浏览:751 |
C语言程序设计教程(第三版)课后习题6.3 (C语言代码)浏览:660 |
【矩阵】 (C++代码)浏览:949 |
C语言程序设计教程(第三版)课后习题5.5 (C语言代码)浏览:556 |
母牛的故事 (C语言代码)浏览:944 |
Tom数 (C语言代码)浏览:527 |
C语言程序设计教程(第三版)课后习题10.1 (C语言代码)浏览:535 |
DNA (C语言代码)浏览:741 |
C语言程序设计教程(第三版)课后习题7.3 (C语言代码)浏览:533 |
WU-C语言程序设计教程(第三版)课后习题12.3 (C++代码)浏览:862 |