DP（動的計画法）で最長増加部分列(LIS)問題を解くまでの過程メモ

なんか連載みたいになってんな

前回はDPでナップザック問題を解きました。

AOJでその次にあった最長増加部分列を解きました。

というか、解けなかったので検索して最長増加部分列(LIS)の長さを求める - Qiitaを見てなるほど〜ってなったのを自分なりにまとめ直したものです。

問題

$N$ 項の数列 $a_0, a_1, \cdots , a_{N-1}$ が与えられたとき、最長増加部分列の長さを求めよ。

（最長増加部分列がなんぞやということについては本家問題ページを読んでください）

制約

$1 \le N \le 100000$
$0 \le a_i \le 10^{9}$

入力

N
a_0 a_1 ... a_N-1

（AOJとは違うが見易さ重視。本質的には一緒なので問題ない）

出力

最大増加部分列の長さを出力する

Ans

DPテーブルの作成

頑張ってDPテーブルの作り方を考えましたが思いつきませんでした。最長増加部分列(LIS)の長さを求める - Qiitaを見て自分なりに再構成した方法でDPテーブルの作成を目指す。

入力例1を考える

5
5 1 3 2 4

これの最長増加部分列は {1, 2, 4}, {1, 3, 4} であるから答えは3。

これから、入力1つごとにグラフ風に最長部分増加列を求めてみる。上記qiitaに書いてあったDPテーブルも併記する。見ればなんとなくわかると思う。

入力 5 → 部分増加列 {5}

f:id:o-treetree:20200525052317p:plain

増加部分列の長さ	1	2	3	4	5
数列の最終要素の最小値	5	INF	INF	INF	INF

入力 1 → 部分増加列 {1}, {5}

f:id:o-treetree:20200525052536p:plain

増加部分列の長さ	1	2	3	4	5
数列の最終要素の最小値	1	INF	INF	INF	INF

後々の受け入れをしやすくするため 1 を上に出す

+入力 3 → 部分増加列 {1}, {3}, {5}, {1,3}

f:id:o-treetree:20200525053843p:plain

増加部分列の長さ	1	2	3	4	5
数列の最終要素の最小値	1	3	INF	INF	INF

入力 2 → 部分増加列 {1}, {2}, {3}, {5}, {1,2}, {1,3}

f:id:o-treetree:20200525054148p:plain

増加部分列の長さ	1	2	3	4	5
数列の最終要素の最小値	1	2	INF	INF	INF

入力 4 → 部分増加列 {1}, {2}, {3}, {4}, {5}, {1,2}, {1,3}, {1,4}, {2,4}, {3,4}, {1,2,4}, {1,3,4}

f:id:o-treetree:20200525055359p:plain — 下の方は省略

増加部分列の長さ	1	2	3	4	5
数列の最終要素の最小値	1	2	4	INF	INF

なんとなくわかった気がする（せやろか）。新しい入力 $x$ に対する処理を場合分けする。（最長増加部分列(LIS)の長さを求める - Qiitaから表をお借りしました。）

増加部分列の長さ	1	2	...	$j-1$	$j$	$j+1$	...
数列の最終要素の最小値	$a_1'$	$a_2'$	...	$a_{j-1}'$	$a_j'$	INF	...

$a_j' < x$ のとき、DPテーブルの一番右に $x$ を追加する。グラフで言うと一番右の端につなげる。（入力4を受け取ったとき{1,2,4}を作る）
$x < a_j'$ のとき、$a_p \le x < a_q$ となるところを見つけて $a_p = x$ と書き換える。グラフで言うとできるだけ右側の差し込めるところを見つけて乗っ取る。（入力2を受け取った時既存の{1,3}との比較により{1,2}を生成してこれを上に持ってくる）

わかったようなわからないような感じなので、この規則でもう一回最長増加部分列の生成をしてみる。今度の入力は

6
1 5 10 2 3 4

f:id:o-treetree:20200525115517p:plain — 入力1 dp = {1}

f:id:o-treetree:20200525115810p:plain — 入力5 dp = {1,5}

f:id:o-treetree:20200525115950p:plain — 入力10 dp = {1,5,10}

f:id:o-treetree:20200525120939p:plain — 入力2 dp = {1,2,10}

ここで、現時点の最長部分増加列は{1,5,10}だが、今後来る（かもしれない）数字のために2を前に出す

f:id:o-treetree:20200525121139p:plain — 入力3 dp = {1,2,3}

f:id:o-treetree:20200525121644p:plain — 入力4 dp = {1,2,3,4}

なんとなくわかった気がする……。もう一度DPテーブル更新操作を見る

$a_j' < x$ のとき、DPテーブルの一番右に $x$ を追加する。グラフで言うと一番右の端につなげる。（入力4を受け取ったとき{1,2,4}を作る）
$x < a_j'$ のとき、$a_p \le x < a_q$ となるところを見つけて $a_p = x$ と書き換える。グラフで言うとできるだけ右側の差し込めるところを見つけて乗っ取る。（入力2を受け取った時既存の{1,3}との比較により{1,2}を生成してこれを上に持ってくる）

まず、DPテーブルの右端に追加するというのは可変長配列vectorへのpush_backで実装できる。「$a_p \le x < a_q$ となるところを見つけて」というのはlower_boundで実装できる。DPテーブルは常に単調増加（<）しているので。

実装

もうDPなんだかようわからんくなってきたけど今までのことをコードにしてみます。$a_j' < x$ のときは、lower_boundの返り値がdp.end()を指す、ということで判定できる

#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
#define pb push_back
#define all(v) (v).begin(), (v).end()

int main(){
  int N;
  cin>>N;
  vi a(N);
  for(int i=0; i<N; i++)cin>>a[i];

  vi dp;

  for(int x: a){ //配列aの各値を順番に新規入力 x とする
    auto itr = lower_bound(all(dp), x);
    if(itr!=dp.end()){
      //itrが a_p <= x < a_q となるa_pへのイテレータ
      *itr = x; 
    }else{
      //xが既存のdpテーブルのどの値よりも大きい
      dp.pb(x);
    }
  }

  int ans = dp.size();
  cout<<ans<<endl;
}