syuntoku14の進捗

進捗を書きなぐります

AOJでPythonに慣れる(20問目)

問題
The Shortest Path on A Rhombic Path
所感
・簡単な動的計画法
pythonの文法に躓くこと多し

躓きポイント:スライスは[2:20000]みたいに範囲外でも受け付けてくれるけど、[-1:20000]みたいに負の数は末尾からのカウントになる

コード

INF=1e8
path=[]
dp=[]
while(True):
    try:
        temp=list(map(int,input().split(',')))
        path.append(temp)
        dp.append([INF for i in range(len(temp))])
    except:
        break
dp[0][0]=path[0][0]
for i in range(1,len(dp)):
    for j in range(len(dp[i])):
        if len(dp[i])>len(dp[i-1]):
            start=0 if j-1<0 else j-1
            dp[i][j]=max(dp[i-1][start:j+1])+path[i][j]
        else:
            dp[i][j]=max(dp[i-1][j:j+2])+path[i][j]
print(dp[-1][-1])