[伯俊/python/2579]階段を登る
5234 ワード
質問リンク:階段を登る
dpアルゴリズムを習い始めたばかりの頃に触れたタイプは階段を登ることです.これはdp問題の基本的な問題だと思います.基本的な問題と違いは、一歩一歩踏み出すと3回連続できないことです.
n=int(input())
stair=[0]*(301)
dp=[0]*(301)
for i in range(n):
stair[i]=int(input())
dp[0]=stair[0]
dp[1]=stair[0]+stair[1]
dp[2]=max(stair[1]+stair[2],stair[0]+stair[2])
for i in range(3,n):
dp[i]=max(dp[i-3]+stair[i-1]+stair[i],dp[i-2]+stair[i])
print(dp[n-1])最後の階段を基準に考えていると、前の階段(i-1)を踏んだら、その前に前の階段の前の2つの階段(i-3)を踏んで、前の階段を踏んでいないと最後の階段(i)と前の2つの階段(i-2)を踏んでしまいます.
言葉で表現するのは難しそうです.ノートに書いて解答することをお勧めします.
Reference
この問題について([伯俊/python/2579]階段を登る), 我々は、より多くの情報をここで見つけました https://velog.io/@i_am_developer/백준python2579계단오르기テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol