【アルゴリズム脳トレ】leetcode hard 552 student attendance ii

こんにちは

今回の学びは

・状態を考え、２連続という制約から、最後の文字はなにか？というDPへの発想に繋げられるか？が重要なポイント

問題は。。。

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

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

この問題はめちゃめちゃ考えました。

そして自力では答えはでませんでした。３日間くらい考えたと思います。

最初は、入力で遅刻は２回以内ならOKという勘違いをしており、それも時間ロスにつながったので

問題文を正しく理解することは、とっても大事です！正しくは遅刻は２回連続以内であればOK!です。

https://leetcode.com/problems/student-attendance-record-ii/discuss/431896/Java-solution-with-intuitive-explanation-(easy-to-understand)

の方の解説を何度も見てようやく分かりました。

実装前後でこれは毎回書きましょう。timespace analysis (時間とスペースの分析）は　

最初は、すんなりAとLにペナルティを数値化してナップサックで解けばいいのでは、と発想して

ふうに考えます

が

どうもうまくいかなさそう。

というか、今から考えるとドツボにハマっています。スプレッドシートを書くのに何時間かかっとんねん、と苦笑いです。

これだけ進まないと、ボツ案の兆しかもしれませんね。

といことで

選択の木を描きまくってイメージを定着させて、ひらめきを待ちます。

3^Nの木はおおきですねー

ってこの辺で

諦めてDISCUSS見ました。

で

彼の解説は秀逸です。

Let's say we have three arrays,
A[i] is the number of valid records that end with 'A' with length i
P[i] is the number of valid records that end with 'P' with length i
L[i] is the number of valid records that end with 'L' with length i

Let's discuess P[i] first:
if the i day is 'P', then the i-1 day can be 'P' or 'A' or 'L'.
so P[i] = P[i-1]+A[i-1]+L[i-1]

Then L[i]
if the i day is 'L', then i-1 day can be 'P' or 'A' or 'L', but when i-1 day is 'L', we need to avoid three are three consecutive L in the records, which means the i-2 day cannot be 'L', thus when i-1 day is 'L', the i-2 day can only be 'P' or A
so L[i] = P[i-1] + A[i-1] + P[i-2] + A[i-2]

Then A[i], which is a little bit complex

Lが二連続という制約に初めて気がつく！？これは入力をしっかり抑えましょう。とう基本に反していますので反省すべき点でした。