題目描述
上圖給出了一個數(shù)字三角形。從三角形的頂部到底部有很多條不同的路徑。對于每條路徑，把路徑上面的數(shù)加起來可以得到一個和，你的任務(wù)就是找到最大的和。
路徑上的每一步只能從一個數(shù)走到下一層和它最近的左邊的那個數(shù)或者右 邊的那個數(shù)。此外，向左下走的次數(shù)與向右下走的次數(shù)相差不能超過 1。
輸入描述
輸入的第一行包含一個整數(shù) N (1 ≤ N ≤ 100)，表示三角形的行數(shù)。
下面的 N 行給出數(shù)字三角形。數(shù)字三角形上的數(shù)都是 0 至 100 之間的整數(shù)。
輸出描述
輸出一個整數(shù)，表示答案。
輸入輸出樣例
示例
輸入：
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
輸出：
27
運(yùn)行限制
最大運(yùn)行時間：1s
最大運(yùn)行內(nèi)存: 256M文章來源：http://www.zghlxwxcb.cn/news/detail-743354.html
num=int(input())
mapp=[]
for item in range(num):
data=list(map(int,input().split()))
mapp.append(data)
pass
dp=[[0 for i in range(0,j+1)]for j in range(num)]
for item in range(num):
for jtem in range(item+1):
if item==jtem==0:
dp[item][jtem]=mapp[0][0]
pass
if jtem==0:
dp[item][jtem]=mapp[item][jtem]+dp[item-1][jtem]
pass
elif jtem==item:
dp[item][jtem]=mapp[item][jtem]+dp[item-1][jtem-1]
pass
else:
dp[item][jtem]=max(mapp[item][jtem]+dp[item-1][jtem-1],mapp[item][jtem]+dp[item-1][jtem])
pass
pass
pass
if num%2==0:
anss=max(dp[num-1][(num)//2],dp[num-1][(num)//2-1])
pass
else:
anss=dp[num-1][(num)//2]
pass
print(anss)
題目中左右步數(shù)相差不超過一，則說明了最后的答案一定是處于中間的，//表示做除法后向下取整文章來源地址http://www.zghlxwxcb.cn/news/detail-743354.html
到了這里，關(guān)于【數(shù)字三角形】的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
