こんにちは
今回の学びは
・ソートすることで、物事を一方方向に見るだけでよくすることで、+1, -1の制約を一個外している。
（時間配分は5分問題理解=restate&clarify 10分検討multip-sol, analysis, reasons 10分実装 20分振り返り の一文45分構成)をできればgoogle docで笑&真剣。
終始、わからないことは声にだして、明確にしていきましょう。
１，まずは入出力をしっかりおさえましょう。（問題を自分の言葉で復唱すること、わからないことをクリアにすると、前提も声にだすこと）
２，いくつかのソリューションを声にだして出してみましょう。（もちろんtime complexit, space complexityの分析や理由を付け加えて）
３，どれでいくか、一緒に決定しましょう。（理由付きでね、よろしく）
timespace analysis (時間とスペースの分析）は 〇〇です
# duplicated, not sorted. 1 <= x <= 10000 and N <= 20000
# constrain: remove S[i]+1, S[i]-1
# [3, 4, 2]
# {3:3 -> 9
# 4:1 -> 4
# 2:2 -> 4
# }
f(N-1) = max(points)
f(2) = f(0) + f(4) + 4
f(i) = f(S[i]-2) + f(S[i]+2) + S[i]
４、実装しましょう。
時間オーバーなので回答をみた。その上で、もうしこしだとおもった。
もみたけど、方向はよくて、ヒントをみて自力でclearした。
特に、バグがちゃんとみつけれてよかった。この回答を眺めたのが直接のヒントとなった
バグはここにあった！dp[i-1]もわすれてはいけない！
class Solution:
def deleteAndEarn(self, nums: List[int]) -> int:
def f(x): # return maximum point at 1
pass
memo = defaultdict(int)
for x in nums:
memo[x] += 1
memo = { k: k*v for k, v in memo.items() }
print(memo)
N = 10001
maxi = 0
# number of values limited to 1 to 10000
dp = [0] * N
for i in range(N):
if i - 2 >= 0:
#dp[i] = dp[i-2] + memo.get(i, 0) # バグはここにあった！dp[i-1]もわすれてはいけない！
dp[i] = max(dp[i-2] + memo.get(i, 0), dp[i-1])
else:
dp[i] = memo.get(i, 0)
maxi = max(maxi, dp[i])
return maxi
５、エッジケースとサンプルテストを忘れずに！
振り返り
「次のこの問題を解くばあい知っていればよい一つの事実とは？」
ソートすることで、物事を一方方向に見るだけでよくすることで、+1, -1の制約を一個外している。
まとめ
・ソートすることで、物事を一方方向に見るだけでよくすることで、+1, -1の制約を一個外している。
以上です