窃盗—PYTHON

問題の説明

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

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

せいげんじょうけん

この村の家は3軒以上10万軒以下です.
money配列の各要素は1000以下の整数です.

問題を解く

まず,DPというカテゴリでなければならないので,最小単位の問題を見つけ,そこでルールを見つけることが重要である.
問題の説明では、最も重要なルールは「隣接する2つの家が略奪され、警報が鳴る」かもしれません.
この言葉の意味は、3つの家があれば、中間の家が略奪されたときの利益がもっと大きいのか、それとも両側の家が略奪されたときの利益がもっと大きいのかを区別しなければならないということです.
家屋1位の総最大値をdpに格納すると仮定すると、得られないdp[i] = max(현재 집의 이득, 현재집 -1의 이득 + 현재집 +1의 이득 )未来dp[i] = max(현재 집-1의 이득, 현재집 의 이득 + 현재집 -2의 이득 )=dp[i] = max(dp[i-1], money[i]+ dp[i-2])

def solution(money):
    answer = 0
    dp = [0] * len(money)

    for i in range (len(money)):
        dp[i] = max(dp[i-1],money[i] + dp[i-2])
    return max(dp)

しかし問題が発生した.論理は正しいようですが、描いてみましたが、円形構造なので、最後~最初の家で重複が出てきます.n軒ある場合dp[0] = max(dp[n],dp[n-1]+money[0])重複する.だから重複を解消するために、0番目の家の場合と改修されていない場合を比較することができます.

def solution(money):
    dp = [0] * len(money) # 0번째 집을 털지 않은 경우
    dp[1] = money[1]
    
    for i in range (2,len(money)):
        dp[i] = max(dp[i-1],money[i] + dp[i-2])
    
    dp1= [0] * len(money) # 0번째 집을 털 경우
    dp1[0] = money[0] 
    dp1[1] = max(dp1[0],money[1])
    
    for i in range (2,len(money)-1):
        dp1[i] = max(dp1[i-1],money[i] + dp1[i-2])
    
    
    return max(max(dp),max(dp1))