いいものをつくろう

CTOの日記

アルゴリズム

【アルゴリズム脳トレ】leetcode hard 97 interleaving string

投稿日:

こんにちは

今回の学びは

ベルマンで全体のざっくり設計、サンプルを手にテーブルを書きつつ、 実際の意味をシッカリ抑えながら、方策関数、価値関数を考える。

理解の最重要ポイントは状態をしっかり書く。

 

問題はhard interleaving-string

(時間配分は5分問題理解 10分検討 10分実装  20分振り返り の一文45分構成)

まずは入出力をしっかりおさえましょう。

 

dpのパターンを勉強している中で

この問題も何回か挑戦しました。パットは解けない問題です。

繰り返し、この問題に戻ってきてやっと解けました。

直前にベルマン方程式を勉強して、その考え方が身についた

のも手がかりの大きなところです。

あとは、DAGっぽくなるので、これはdpできるだろうという考えも手がかりでした。

 

なんどか、サンプルで表を作ったりして

も、うまく正解に導く価値関数がつくれません。うまくはまらない って感じですね。

そこで

もう一度言葉で攻めます。動的計画法に必要な

あのパターンを考えて言葉にして書いてみる、作業します。すると

という感じでs,

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 (時間とスペースの分析)は ◯◯

 

「次のこの問題を解くばあい知っていればよい一つの事実とは?」

理解の最重要ポイントは状態をしっかり書けるか?

 

まとめ

ベルマンで全体のざっくり設計、サンプルを手にテーブルを書きつつ、 実際の意味をシッカリ抑えながら、方策関数、価値関数を考える。

理解の最重要ポイントは状態をしっかり書く。

以上です

-アルゴリズム

Copyright© CTOの日記 , 2020 All Rights Reserved.