こんにちは
今回の学びは
・ベルマンで全体のざっくり設計、サンプルを手にテーブルを書きつつ、 実際の意味をシッカリ抑えながら、方策関数、価値関数を考える。
・理解の最重要ポイントは状態をしっかり書く。
問題はhard interleaving-string
（時間配分は5分問題理解 10分検討 10分実装 20分振り返り の一文45分構成)
まずは入出力をしっかりおさえましょう。
dpのパターンを勉強している中で
この問題も何回か挑戦しました。パットは解けない問題です。
繰り返し、この問題に戻ってきてやっと解けました。
直前にベルマン方程式を勉強して、その考え方が身についた
のも手がかりの大きなところです。
あとは、DAGっぽくなるので、これはdpできるだろうという考えも手がかりでした。
なんどか、サンプルで表を作ったりして
も、うまく正解に導く価値関数がつくれません。うまくはまらない って感じですね。
そこで
もう一度言葉で攻めます。動的計画法に必要な
あのパターンを考えて言葉にして書いてみる、作業します。すると
という感じでｓ，
S3[i] i番目の文字がs1, s2どっちかの先頭にあるか？ というような価値観数ができそう
今回の理解の最重要ポイントは状態をしっかり書けたことです。ノートにあるように、
状態はS1が残っているか？S2が残っているか？S3[i]がs1かs2の先頭にあるか？と一つ一つ丁寧にに書いているとこです。
これがDPを書く、準備となりました。
というところまできました。実際は更に細かく認識・理解できていないと
とけないのですが、これは大きな一歩で、正解への道でした。
うえのアイデアでもう一回サンプルを回して、ひょうを書きながら
考え、つづけること15分くらいで、
やって以下にある方策関数が導けました！
とくにこの方策関数がちゃんと整理できる
までが長いです。いつも。。。（汗）
基本はS3のi番目の文字列が現在の訪れているrow, columnに対応する文字列のいづれかと一致するか？
というもの。上で、S3[i] i番目の文字がs1, s2どっちかの先頭にあるか？ と表現した部分です。
もっと掘り下げて考えると、
左がTってことは、そのRow(つまりはS2）は選択積みなので、S3[i]にあたる文字は列のS1の先頭でないといけない。
反対に、
上がTってことは、S2の先頭
で、実は上も左もTの場合もあって、それはどっちゃでもいい。
ただし、自力で方策関数を見つけ出すよいう体験は何ものにも変えがたい。
ベルマンで全体のざっくり設計、サンプルを手にテーブルを書きつつ、 実際の意味をシッカリ抑えながら、方策関数、価値関数を考える。
これが私の考える、DPの王道である。
実装前後でこれは毎回書きましょう。timespace analysis (時間とスペースの分析）は O(N^2)
pseudocode（擬似コード）をかいてみますか。
。。。
実際の実装はこちら
実装後です。timespace analysis (時間とスペースの分析）は ◯◯
「次のこの問題を解くばあい知っていればよい一つの事実とは？」
理解の最重要ポイントは状態をしっかり書けるか？
まとめ
・ベルマンで全体のざっくり設計、サンプルを手にテーブルを書きつつ、 実際の意味をシッカリ抑えながら、方策関数、価値関数を考える。
・理解の最重要ポイントは状態をしっかり書く。
以上です