おはようございます
DP問題は言葉にしてきれいにハマる漸化式を考え出すのが難しいです
ですが
漸化式をつくるポイントを抑えておけば
DP攻略の確率はグッとあがるでしょう。
本記事では
これまでのDP問題への取り組みからの学びを完結にまとめ
・【アルゴリズム脳トレ】leetcode medium 300 longest increasing subsequence
・【アルゴリズム脳トレ】leetcode medium 1143 longest common subsequence
次回以降のDP問題へのマニュアルとすることです
早速ですが
手順です
１，総当りでまずは考える。
２，問題を小さく（往々に入力を小さく）して、その答えが次にその入力を大きくしたときのベースとしてつかえるか？をかんがえる。
３，２でできそうなら漸化式をかんがえる
３−a、漸化式の大枠を考える。サブケースの解がでたとして、入力が１増えた時の答えはどうなりうるのか？をかんがえる。ポイントは俯瞰して高い視点で考えるです。
つまり、L[i] = L[i-1] から 1 増えるか 否かの2パターンしかない！
ということだ。ここは必ずおさえたいポイントです。
さらに、ベースにするサブケースはどれなのか？も注意する必要があります。単純に一個目の
サブケース(i-1とか）でいいのか、(i-1,j-1)なのかしっかり丁寧に考える必要あります。それができないとLCS問題で迷走したことがわかる記事のように迷走したりします。
３-b、漸化式の大枠が上にように2パターンとか複数あるなら、それぞの条件をかんがえる。つまり、サブケースの解がでたとして、入力が１増えた時の、答えを求める判断基準を明確にする、といこと。
３-c、漸化式の変数をきめる。覚えておかないと行けないのは何か？あきらかなのは、目的変数でこれはLCS数とかLIS数とかで、答えだ、あるいわLCS数ではなくLCS列の場合もあるかもしれない。サブケースをの計算を重ねる途中で、どんな中間情報が必要か？dp表どのように収まるかは考えずに、まずは必要な情報は何だ？と考えるのがポイントです
変数を減らすためのチップは例えば連続という特性を活かすなどがあります。これらはテクニックです、自分のストックを増やしていきましょう。
要は書き出したいのは
漸化式の大枠・パターン そして 答えを求める判断基準
LIS最大昇順列数の問題でいうならばで、式 一本であらわせます
L(i) = 1 + max( L(j) ) where 0 < j < i and arr[j] < arr[i]; or L(i) = 1, if no such j exists.
大枠というのは、 1 + xxxxx L (j) のように、サブケースに +1 か +0 しかありえへんやろ！という発見で
答えをもとめる判断基準は、 xxxx L (j) のようなおぼろけではなく。 max ( L(j) ) で jというのは 0 < j < iを満たしてないといけないし、arr[j] < arr[i]でないといけない、といった詳細です。
この記事は、
今後さらにdp問題を重ねるにつれて改訂していきます。
ちなみに私はdpまで初心者レベルで比較的簡単な問題しか解けていません。
もっと経験値が高いひとの解説は非常に参考になるのでレベルにあわて参照できます
以上です