[リートコード] 0198. 住宅強盗

Python、C++、JavaScript、SQL、TypeScript の多様な LeetCode ソリューションを探索してください。面接の準備、学習、複数のプログラミング言語でのコードの練習に最適です。 Github リポジトリリンク

中くらい

あなたは通り沿いの家々への強盗を計画しているプロの強盗です。各家には一定量の現金が隠されています。各家への強盗を阻止する唯一の制約は、隣接する家々にセキュリティシステムが接続されているということです。 同じ夜に隣接する2軒の家に侵入された場合、自動的に警察に通報します。.

整数配列が与えられた場合 数字 各家の金額を表し、リターン今夜あなたが強奪できる最大金額 警察に通報せずに.

例 1:

入力： 数値 = [1,2,3,1]
出力： 4
説明： 家 1 (お金 = 1) を強盗し、次に家 3 (お金 = 3) を強盗します。強盗できる合計金額は 1 + 3 = 4 です。

例 2:

入力： 数値 = [2,7,9,3,1]
出力： 12
説明： 強盗ハウス 1 (お金 = 2)、強盗ハウス 3 (お金 = 9)、強盗ハウス 5 (お金 = 1) で強盗できる合計金額 = 2 + 9 + 1 = 12。

制約:

1 <= nums.length <= 100
0 <= nums[i] <= 400

パイソン

				
					# 時間計算量: O(n) # 空間計算量: import リスト クラスの入力による O(1) 解決策: def __init__(self) -> なし: self.memo = {} def rob(self, nums: List[int]) -> int: self.memo = {} return self.robFrom(0, nums) def robFrom(self, i, nums): if i >= len(nums): return 0 if i in self.memo: return self. memo[i] self.memo[i] = max(self.robFrom(i+1, nums), self.robFrom(i+2, nums) + nums[i]) return self.memo[i] nums = [ 1、2、3、1] print(Solution().rob(nums))

パイソン

関連記事