[プログラマー/Python](ダイナミックプランニング)窃盗
989 ワード
ソース
泥棒はある村を強奪しようとしている.この村のすべての家は下図のように丸く配置されている.
各家には隣接する家と防犯装置が接続されているため、隣接する家を2軒強奪すると警報が鳴る.
どの家にもお金が入った並びのお金がある場合は、泥棒が盗むことができるお金の最高価格を返すために解関数を書いてください.
この村の家は3つ以上100000軒以下です. money配列の各要素は1000以下の整数である.
moneyreturn[1, 2, 3, 1]4
問題の説明
泥棒はある村を強奪しようとしている.この村のすべての家は下図のように丸く配置されている.
各家には隣接する家と防犯装置が接続されているため、隣接する家を2軒強奪すると警報が鳴る.
どの家にもお金が入った並びのお金がある場合は、泥棒が盗むことができるお金の最高価格を返すために解関数を書いてください.
せいげんじょうけん
I/O例
moneyreturn[1, 2, 3, 1]4
説明する
def solution(money):
result1 = []
result2 = []
result1.append(money[0])
result1.append(max(money[0],money[1]))
result2.append(0)
result2.append(money[1])
for i in range(2, len(money)-1):
result1.append(max(money[i]+result1[i-2],result1[i-1]))
for j in range(2,len(money)):
result2.append(max(money[j]+result2[j-2],result2[j-1]))
return max(max(result1),max(result2))
Reference
この問題について([プログラマー/Python](ダイナミックプランニング)窃盗), 我々は、より多くの情報をここで見つけました https://velog.io/@chaegil15/프로그래머스파이썬-동적계획법Dynamic-Programming-도둑질テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol