藍橋杯算法提高VIP-奪寶奇兵

題目描述

在一座山上,有很多很多珠寶,它們散落在山底通往山頂的每條道路上,不同道路上的珠寶的數目也各不相同.下圖為一張藏寶地圖:

7
3  8
8  1  0
2  7  4  4
4  5  2  6  5
           

”奪寶奇兵”從山下出發,到達山頂,如何選路才能得到最多的珠寶呢?在上圖所示例子中,按照5-> 7-> 8-> 3-> 7的順序,将得到最大值30

輸入

第一行正整數N(100> =N> 1),表示山的高度

接下來有N行非負整數,第i行有i個整數(1< =i< =N),表示山的第i層上從左到右每條路上的珠寶數目

輸出

一個整數,表示從山底到山頂的所能得到的珠寶的最大數目.

樣例輸入

5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
           

樣例輸出

30

n = int(input())
mapL = [list(map(int,input().split())) for _ in range(n)]
dp = []
for i in range(n):
    dp.append([0]*(i+1))
dp[0][0] = mapL[0][0]
for i in range(1,n):
    for j in range(0,len(mapL[i])):
        if j == 0:
            dp[i][j] = dp[i-1][j] + mapL[i][j]
        elif j == len(mapL[i]) - 1:
            dp[i][j] = dp[i-1][j-1] + mapL[i][j]
        else:
            dp[i][j] = max(dp[i-1][j],dp[i-1][j-1]) + mapL[i][j]

print(max(dp[n-1]))