paizaラーニング問題集「最長部分増加列」を解いてみた

▼感想

自分で色々考えて実装したものの、
なかなかスコアが100にならなかったため、
ヒントを見て理解し実装しました。
本記事の下部に理解した内容をメモとしてまとめました。

▼コード

########## 処理0(準備) インプット,リスト定義など ###########

n = int(input())

a = [0]*n

########## 処理1 漸化式の定義、計算、出力 ##########

dp = [0]*n

dp[0] = 1

for i in range(n):
    a[i] = int(input())

for i in range(1,n):
    dp[i] = 1
    for j in range(i):
        if a[j] < a[i]:
            dp[i] = max(dp[i],dp[j]+1)

print(max(dp))

▼変数に関するメモ

・a=[3,1,4,1,5,9,2,6]
木が8本横並びで存在し、aはそれぞれの木の高さ(cm)を表すリスト。
a[0]は左端から1番目に存在する木の高さ。
　
・dp=[0,0,0,0,0,0,0,0]
木の高さが左端から単調増加しているか？を考える。
その木が単調増加の末尾にあると仮定したとき、(その木を含め)単調増加に含めることができる木の本数の最大値を格納するリスト。

初期値はすべて0だが、処理後は以下のようになる。
dp=[1,1,2,1,3,4,2,4]

・i=1～7
(外側のloopのi)dpを先頭から末尾まで走査する変数。
(内側のloopのi)単調増加の末尾に存在する木の番目を示す変数。

・j=0～i
(内側のloop)単調増加の末尾に存在する木と比較する木の番目を示す変数。

▼i=4のときの処理に関するメモ

i=4(to8)

dp[4]=1

　j=0(to4)
　　a[0] ? a[4] (3<5につきTrue)
　　dp[4]=max(dp[4],dp[0]+1)=max(1,2)=2

　j=1(to4)
　　a[1] ? a[4] (1<5につきTrue)
　　dp[4]=max(dp[4],dp[1]+1)=max(2,2)=2

　j=2(to4)
　　a[2] ? a[4] (4<5につきTrue)
　　dp[4]=max(dp[4],dp[2]+1)=max(2,3)=3

　j=3(to4)
　　a[3] ? a[4] (1<5につきTrue)
　　dp[4]=max(dp[4],dp[3]+1)=max(3,2)=3

　j=4(to4) Inner loop finished.

▼ dp[i]=max(dp[i],dp[j]+1) の処理に関するメモ

max関数の2項目 dp[j]+1
j番目の木がi番目の木より小さいならば、
j番目の木までの単調増加に1つ木を加えることができる。
dp[i]の初期値は1なので、
max関数を用いることで2項目(dp[j]+1)の値でdp[i]を更新できる。