PythonのHouseRobber

都市があり、都市の各家に一定の金額があるとします。ある強盗は一晩でお金を奪いたいと思っています。市には1つのセキュリティシステムがあります。つまり、同じ夜に2つの連続した家が壊れた場合、自動的に警察に通報します。だから私たちは強盗が奪うことができる最大量を見つける必要がありますか？

1つの配列が提供されます。インデックスiで、A[i]はi番目の家に存在する量です。配列が次のようになっていると仮定します：A =[2、7、10、3、1]、結果は13になります。最大値はhouse1（値2）、house3（値10）、およびhouse5（値1）から取得されます。 ）、合計は13

これを解決するために、このアプローチに従います-

• prev1：=0およびprev2=0を取得
• i=0からAの長さ-
  • temp：=prev1
  • prev1：=prev2 +A[i]およびprev1の最大値
  • prev2 =temp
• prev1を返す

例

理解を深めるために、次の実装を見てみましょう-

class Solution(object):
   def rob(self, nums):
      """
      :type nums: List[int]
      :rtype: int
      """
      prev2 = 0
      prev1 = 0
      for i in range(0,len(nums)):
         temp = prev1
         prev1 = max(prev2+nums[i],prev1)
         prev2 = temp
      return prev1
ob1 = Solution()
print(ob1.rob([2,7,10,3,1]))

入力

nums = [2,7,10,3,1]

出力

13