最長増加部分列(LIS)の解法 ── AOJ 2430 対応の動的計画法
飛ばしてよいぶん、組み合わせが多すぎる
[10, 9, 2, 5, 3, 7, 101, 18] から、順番はそのままに要素を間引いて、増え続ける並びを作ります。一番長いもので何個取れるかが答えです。この場合は 2, 3, 7, 18 の 4 個です。
間引いてよい、というのが厄介です。連続した区間を切り出すだけなら候補は数千通りで済みますが、飛ばしてよいなら「取る・取らない」の組み合わせで 2 の n 乗になります。8 個で 256 通り、40 個で 1 兆通りです。
なお、間引ける並びを部分列、連続した区間を部分配列と呼びます。名前が似ているので、どちらの話をしているのかは常に確かめてください。
「ここで終わる」と決めてしまう
組み合わせが爆発するのは、どこから始まってどこで終わるかを両方とも自由にしているからです。片方を固定します。
「i 番目の要素で 終わる 増加列のうち、一番長いものの長さ」を考えます。終わりを固定すると、i の答えは自分より前だけを見れば決まります。自分より前で、自分より小さい値の要素を探し、その要素で終わる答えのうち一番大きいものに 1 を足すだけです。誰の後ろにも付けないなら、自分 1 個で長さ 1 です。
前の答えしか使わないので、左から順に決めていけます。
Python
nums = [10, 9, 2, 5, 3, 7]
i = 5 # nums[i] は 7
for j in range(i):
if nums[j] < nums[i]:
print(j, nums[j], "の後ろに付けられる")7 の後ろに付けられるのは 2、5、3 の 3 つです。このうち一番長い答えを持っているのは 5 と 3 (どちらも長さ 2) なので、7 で終わる答えは 3 になります。
左から順に見ていくと、10 は 1、9 も 1、2 も 1、5 は 2、3 も 2、7 は 3。最後に全部の中の最大を取れば、それが答えです。要素ごとに前を全部見返すので手数は要素数の 2 乗で、40 個なら 1,600 回ほど。先ほどの 1 兆通りとは比べものになりません。最後の要素の答えが最大とは限らない ので、この一手を忘れないでください。[1, 2, 3, 0] なら、末尾の 0 の答えは 1 ですが、全体の答えは 3 です。
増加は「厳密」
同じ値は増加とみなしません。[7, 7, 7, 7] の答えは 1 です。比較を <= で書くと 4 になってしまうので、< を使います。ここはテストで必ず落ちる場所です。
もう 1 つ、空の配列を渡されたときに、全体の最大を取る処理が空を見て落ちることがあります。長さを先に確かめておくと安全です。
やってみよう
[0, 1, 0, 3, 2, 3]の答えは 4。どの 4 つか、指で追ってみる[5, 4, 3, 2, 1]は 1。減り続けているので、どれも誰かの後ろに付けられない[1, 3, 6, 7, 9, 4, 10, 5, 6]を左から手で追う。答えは 6
要件
- 戻り値は厳密増加部分列の最大長 (整数)
- DP 配列 dp[i] = i 番目で終わる LIS の長さ、として O(n^2) で求めること
- 等しい値は増加とみなさない (nums[j] < nums[i] を満たす場合のみ伸ばす)
入出力例
lengthOfLIS([10,9,2,5,3,7,101,18]) → 4
lengthOfLIS([0,1,0,3,2,3]) → 4
lengthOfLIS([7,7,7,7]) → 1
lengthOfLIS([1,2,3,4,5]) → 5
lengthOfLIS([5,4,3,2,1]) → 1
lengthOfLIS([42]) → 1ヒント
