TIL #16 - 3.18

ダイナミックプランニング法ダイナミックプランニング法:特定の問題を分割してアルゴリズムを解く形式
GRADYアルゴリズムとの違いは?グリディアルゴリズムは既存の状況で最適解を見つけようとした.
動的計画法:すべての場合の数を考慮し、最適な解を探します.
動的計画(動的計画タイプ):
通常は連続して現れるパターンがあります.このモードを再帰関数に分解しますが、これらの値を覚えて演算を減らします.
有名な例)フィボナッチ数列
Fibo(1) = 1
Fibo(2) = 2
Fibo(3) = Fibo(2) + Fibo(1)
Fibo(N) = Fibo(N-1) + Fibo(N-2)
fibo(N)値のために再帰関数として演算を続け,fibo 1またはfibo 2値に達したら,脱出条件式を書き出し,動的プランニングアルゴリズムを記述すればよい.
どうてきけいかくほうもんだい
質問する
階段を登るゲームは階段の下の起点から階段の先端の終点までのゲームです.図1>に示すように、階段ごとに一定の点数が書かれており、階段を踏むと階段の点数が得られます.
<図2>に示すように、始点から、第1、2、4、6段の階段を歩いて終点に着き、合計10+20+25+20=75点となる.
階段を登るには以下のルールがあります.
階段は一度に1段または2段上がることができます.つまり、階段に沿って、次の階段を上ったり、次の階段を下りたりすることができます.
連続した3つの階段を踏んではいけない.しかし、起点は階段には含まれていません.
最後に着いた階段は必ず踏まなければなりません.
そのため、最初の階段に沿って、2番目か3番目の階段を歩くことができます.しかし、最初の階段を踏んで4番目の階段を登ったり、最初の階段、2番目の階段、3番目の階段を連続して踏んだりすることはできません.
各段階の点数を与える場合は、ゲームの総点数の最値を求めるプログラムを作成します.
入力
入力した最初の行には、階段の数が表示されます.
2行目から、1行1つ、一番下の階段から、各階段に書いてある点数を順番にあげます.階段の個数は300以下の自然数で、階段に書いてある点数は10000以下の自然数です.
しゅつりょく
1行目に階段を登るゲームで得られる総得点の最値を出力します.
#2579号-階段を登る(#dynamic programming)
下から上に向かって考えると状況の数が複雑になるので、下から上に落ちるとどんな状況になるか考えてみましょう.
#1.前の段(n-1)が連続して世界段を歩くことができず、前の段の後に残りのd(i-3)値を計算する回数
#2.前段を踏んで残りd(i-2)値を算出するときの仮数
1と2を選択して最大値を返します.

import sys
N = int(sys.stdin.readline())
score = [0]      #score를 받을 수 있는 리스트 생성. 0을 넣은 이유는 d[0]은 0번째 게단을 의미. 값이 없기때문에, 첫번째 계단부터 값을 받아주기 위해서 score.append(sys.stdin.readline())을 해준다.
d = [0] *301     #마찬가지로 d[0]은 존재하지않는다. 그렇기 때문에 [0]안에 있는 원소를 300개 대신 301개를 만들어준다.

for _ in range(N):
    score.append(int(sys.stdin.readline())) #입력값을 순서대로 받아서 (첫번째 계단 value, 두번째 계단 value) score값에다가 append시켜준다

if N > 0:  
    d[1] = score[1] # N>0보다 크다면 즉, d[1] = score[1]. 첫계단을 밟는데 경우의 수는 없다

if N > 1:
    d[2] = score[1] +score[2] #N> 1보다 크고 d[2]값을 찾는다면 max-score는 무조건 첫번째 계단 두번째 계단 둘다 밟는것이다. 그렇기 때문에 d[2] = score[1] + score[2]로 식을 세울 수 있다.

for i in range(3, N+1):
    d[i] = max(score[i] + score[i-1]+ d[i-3], score[i] + d[i-2]) #dynamic programming 활용, d[1] & d[2] 값을 기억해서 반환, 재귀문제(?)


print(d[N])