[プログラマー]窃盗/python/ダイナミックプログラミング(DP)

盗みを働く

問題の説明

泥棒はある村を強奪しようとしている.この村のすべての家は下図のように丸く配置されている.

各家には隣接する家と防犯装置が接続されているため、隣接する家を2軒強奪すると警報が鳴る.
どの家にもお金が入った並びのお金がある場合は、泥棒が盗むことができるお金の最高価格を返すために解関数を書いてください.

せいげんじょうけん

この村の家は3つ以上100000軒以下です.

money配列の各要素は1000以下の整数である.

解答方法

それぞれ

の第1軒の家と第2軒の家を求めて、そしてもっと大きい価格を返します.

i 1軒目の家を略奪していない(=i-1軒目の家を略奪している場合)と1軒目の家を略奪している場合(=i-2軒目の家を略奪している場合)を比較し、価格を更新すればよい.dp[i] = max(dp[i - 1], dp[i - 2] + money[i])

def solution(money):
    n = len(money)
    
    # 첫번째 집을 터는 경우
    dp = [0] * n
    dp[0] = money[0]
    dp[1] = dp[0] # 두번째 집을 털 수 없으므로 그대로 dp[0]
    for i in range(2, n - 1):
        dp[i] = max(dp[i - 1], dp[i - 2] + money[i])
    sum1 = dp[-2] # 첫번째 집을 털었으면, 마지막에서 두번째 집까지 털 수 있음
    
    # 두번째 집을 터는 경우
    dp = [0] * n
    dp[0] = 0
    dp[1] = money[1]
    for i in range(2, n):
        dp[i] = max(dp[i - 1], dp[i - 2] + money[i])
    sum2 = dp[-1] # 두번째 집을 털었으면, 마지막 집까지 털 수 있음
    
    return max(sum1, sum2)