順次追記: 競技プログラミングの知識(DP)
Q. これはなに？
DPで要求された知識や考え方を雑多に書くだけのメモ帳、状態の持ち方とか遷移とかの考え方についてです。
僕は論理的、数学的な正しさを考えるのが苦手なので、体系化していきたい。
ちなみに僕が知ってることは省くので、網羅的ではないです。ゆるして。
部分文字列系のDP
ABC130-E Common Subsequence
とりあえず部分文字列系はs[i] == t[j]かどうかで場合分け！（素振り）
ホントかなあ、大体ホントだと思う。
maspyさんがおっしゃっていたように、dpを意識するというよりも適切に場合分けを考えることが大切で、場合分けした際に小問題が出てくると漸化式が作れてdpが出来ると。
この問題はそれをよく表している気がする。
で、これの本質は「Sのi文字目とTのj文字目が同じ時（これをCとする）、Sのi-1文字目とTのj文字目までに出来た全ての部分文字列の末尾にCを付けたものが新たに部分文字列となる」こと。
つまり「Sのi文字目とTのj文字目が同じ時における部分文字列の数は、それまで（Sのi-1文字目とTのj-1文字目まで）に出来た部分文字列の数になる」ということなんですね。
なので
のとき
となるんですねえ！（見づらい）
これを実装します。おわり。
そのまま辺を貼ると辺の数が
とかになって死亡するけど、セグ木で上手いこと出来るやつ
ABC146-F Sugoroku
知ってるとやるだけ。
という遷移になる。
筆算をDPでシミュレーションするやつ
これ苦手なんだよね、筆算で何をしているかを知っていると理解が捗るのかな。
僕は筆算の理屈をよく知らないので、毎回困っちゃう。
ABC135-D Digits Parade
割り算の筆算を考えると遷移がわかる（は？）
応用できないんだよね。
ABC155-E Payment
引き算の筆算を分かっていると出来るのですが、僕は引き算の筆算を雰囲気でしか解いていないので、破滅。
係数かけてうまいこと遷移するやつ
遷移するごとに適当な係数をかけていくといいやつ。適宜係数を求めながらどう計算量を落とすかがカギ
キーエンスプログラミングコンテスト2021 C Robot on Grid
本質は「遷移に関係ない空白の数だけ3をかける」なんだけど、それを間に合うようにうまくやるのが難しい。
解説では「遷移に関係ない空白の数だけ3をかける」⇒「初期の係数を遷移に関係ない空白の数だけ取っておいて、空白マスを踏むごとに係数を3で割る」という方法を模範解答としている。
なお、くるさんに教えてもらったがマンハッタン距離が同じなところは独立に係数の計算ができるので、DPしながらマンハッタン距離が同じところの3の数をかけていく方法などもある。いわれるとそうだねって感じ。
