こんにちは
今回の学びは
・おもいつくアルゴリズムの消去法で掘り下げよう。
問題は。。。
（時間配分は5分問題理解 10分検討 10分実装 20分振り返り の一文45分構成)
まずは入出力をしっかりおさえましょう。
問題を理解してからの思考の流れはこう
１、最初、サンプルをみてパターンをみいだそうと２，３パターン書き出す
・その中で
２、おっ、greedyではできないなと。
３，おっ、奇数、偶数indexペアだけとる方法をダメだなと。
おもいつくアルゴリズムを消去していった
このあたりでdpなのか？
とかんがえる。
最初はdp表のつくりかたはどうするんだ？とかんがえる
くわしくはDP問題を解くときの考え方マニュアルをみる。
で、ちょっとなやんだあと
あ！っと。ひらめく。
単純にこれまでの結果があったとして、漸化式がくめそーだと。
できた。
O(n)の解放
実装前後でこれは毎回書きましょう。timespace analysis (時間とスペースの分析）は O(n)
pseudocode（擬似コード）をかいてみますか。
。。。
今回は直接leetcodeにかいてみて、一発で通りました
実際の実装はこちら
class Solution:
def rob(self, nums: List[int]) -> int:
length = len(nums)
if length <= 0: return 0
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以外で再試行
for i in range(length):
dp[i] = max(dp_get(i-1), dp_get(i-2)+nums[i])
return dp[i]
実装後です。timespace analysis (時間とスペースの分析）は O(n)でスペースもO(n)です
メモでコメントでかきましたが、
dpダメならと、次の手順にも目を向けているあたりは成長しているなと感じます。
まとめ
・おもいつくアルゴリズムの消去法で掘り下げよう。
以上です