こんにちは
今回の学びは
・ある程度型、パターンを覚えて、解く・閃く速度をあげよう （これ結構大事かも）
・配列がサイクリックになったら、ズラして２パターンを解く
問題は。。。
（時間配分は5分問題理解 10分検討 10分実装 20分振り返り の一文45分構成)
まずは入出力をしっかりおさえましょう。
leetcode easy 198 house robberという問題で
与えられた配列はサイクリックであるとう違いのみです。
ですが
この違いを埋めるアイデアの思いつきは結構難しかったです
例のごとくエクセルにdp表を書きながらあーだ、こーだしました。
何かしらの筆跡はわかると思いますが、（これくらいのサンプルをあーだこーだした様子がわかると思うので、後の自分の参考になる
と思ってスクショしています。）最後の方で
top includedしたバージョンと、その場合の答えはi-1
top excludedしたバージョン この場合の答えはi
というしたらいけそうだということが分かり、それがそのまま正解となった
最初の数字を使ってしまうと、それが伝搬されて最終的に最後の数字が使えなくなる。
だから
どうしたらいいんだ？的な発想が発見につながったと思います
肝は最初の数字が貢献すると最後は使えない
ということですね。
最初の25分では思いつきませんで、さらに悩むこと15分くらいしたかと思います
思いつきのスピードをあげるにはどうしたらいいのでしょうか？
＝＞できる人は型でと行っている記事もあるくらいなので、まぁ、パターンを自分のDBに貯めていくことをやってみましょうか。
ということで今日の私のパターンDBには配列がサイクリックになったら、ズラして２パターンを解く
と追加しました
実装前後でこれは毎回書きましょう。timespace analysis (時間とスペースの分析）は O(n)
pseudocode（擬似コード）をかいてみますか。
。。。
実際の実装はこちら
class Solution:
@timeit
def rob(self, nums: List[int]) -> int:
length = len(nums)
if length <= 0: return 0
if length <= 3: return max(nums)
# length >= 4
dp = [0] * len(nums)
def dp_get(i, default=0):
if i < 0 or i >= length: return default
else: return dp[i]
# dp的にiまでの配列をつかった最大をほりこんでいけたと仮定(hypoth1)する
# その上で漸化式をつくる
# hypothXが可能か検討する yesなら実装 noならdp以外で再試行
# Top included
for i in range(length):
dp[i] = max(dp_get(i-1), dp_get(i-2)+nums[i])
maxi = dp[i-1]
# Secound round without top
dp[0] = 0 # bit of initializtion
for i in range(1, length):
dp[i] = max(dp_get(i-1), dp_get(i-2)+nums[i])
return max(maxi, dp[i])
実装後です。timespace analysis (時間とスペースの分析）は O(n)でスペースもO(n)です
メモでコメントでかきましたが、
dpダメならと、次の手順にも目を向けているあたりは成長しているなと感じます。
速度は十分出たので満足です
メモリに関しては成績はよくないですが、他の人はdp使わずに解いたということでしょうか。
まとめ
・ある程度型、パターンを覚えて、解く・閃く速度をあげよう （これ結構大事かも）
・配列がサイクリックになったら、ズラして２パターンを解く
以上です