[Programmers/Python/ダイナミックプランニング]-盗難

ソース:https://programmers.co.kr/learn/courses/30/lessons/42897

Q.

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

各家には隣接する家と防犯装置が接続されているため、隣接する家を2軒強奪すると警報が鳴る.
どの家にもお金が入った並びのお金がある場合は、泥棒が盗むことができるお金の最高価格を返すために解関数を書いてください.
せいげんじょうけん
この村の家は3軒以上10万軒以下です.
money配列の各要素は1000以下の整数です.
I/O例
money return
[1, 2, 3, 1] 4

私の答え

1

最初から、最大の家から、その家の両側を排除し、残りの家から最大の方法を選んでコードを書くことを繰り返します.

def solution(money):
    answer = 0
    while (True):
        if sum(money) == -1*len(money):
            break

        now = money.index(max(money))
        answer += money[now]
        money[now], money[(now+1) % len(money)], money[(now-1) % len(money)] = -1, -1, -1
    
    return answer

しかし,質問のテストケースを通して,上記のコードを確認し,[91,90,5,7,5,7]を通して,私のコードが間違っていることに気づいた.
print(「テストケース結果比較(私のコード/答え)」
print(solution([1,2,3,1]), 4)
print(solution([1,1,4,1,4]), 8)
print(solution([1000,0,0,1000,0,0,1000,0,0,1000]), 3000)
print(solution([1000,1,0,1,2,1000,0]), 2001)
print(solution([1000,0,0,0,0,1000,0,0,0,0,0,1000]), 2000)
print(solution([1,2,3,4,5,6,7,8,9,10]), 30)
print(solution([0,0,0,0,100,0,0,100,0,0,1,1]), 201)
print(solution([11,0,2,5,100,100,85,1]), 198)
print(solution([1,2,3]), 3)
print(solution([90,0,0,95,1,1]), 185)
print(solution([91,90,5,7,5,7]), 104)

2(通過)

dp 1[n],dp 2[n]:n番目の家を通った瞬間の最高値(nは盗んでもいいし、盗まなくてもいい).
(dp 1)窃盗0軒目
(dp 2)0番目の家を盗まない
最後にmax(dp 1[-1],dp 2[-1])

def solution(money):
    length = len(money)

    # 0 번째 집 훔치는 경우
    dp1 = [0] * (length - 1)
    dp1[0] = money[0]
    dp1[1] = dp1[0]
    for i in range (2, length-1): # 마지막 집은 갈 필요 없다.
        dp1[i] = max(dp1[i-1], dp1[i-2]+money[i])

    # 0 번째 집 훔치지 않는 경우
    dp2 = [0] * length
    dp2[0] = 0
    dp2[1] = money[1]
    for j in range (2, length): # 마지막 집까지 확인해보긴 해야함
        dp2[j] = max(dp2[j-1], dp2[j-2]+money[j])
        
    return max(dp1[-1], dp2[-1])