[リートコード] 0213. ハウス強盗 ii

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

中くらい

あなたは通り沿いの家々への強盗を計画しているプロの強盗です。各家には一定の金額のお金が隠されています。 円形に配置されています。 つまり、最初の家は最後の家に隣接しており、隣接する家にはセキュリティシステムが接続されています。 同じ夜に隣接する2軒の家に侵入された場合、自動的に警察に通報します。.

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

例 1:

入力： 数値 = [2,3,2]
出力： 3
説明： 家 1 (お金 = 2) を強盗してから家 3 (お金 = 2) を強盗することはできません。これらは隣接する家であるためです。

例 2:

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

例 3:

入力： 数値 = [1,2,3]
出力： 3

制約:

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

パイソン

				
					# 時間計算量: O(n) # 空間計算量: import リスト クラスの入力による O(n) 解決策: def rob(self, nums: List[int]) -> int: def robMoney(nums: List[int], start : int, end: int) -> int: dp = [0] * (end - start) dp[0] = nums[start] dp[1] = max(dp[0], nums[start + 1]) for i in range(start + 2, end): dp[i-start] = max(nums[i] + dp[i-start - 2], dp[i-start - 1]) return dp[-1] n = len(nums) n == 0の場合: 0を返します n == 1の場合: nums[0]を返します n == 2の場合: max(nums[0], nums[1])を返しますmoney1 = robMoney(nums, 0, n - 1)money2 = robMoney(nums, 1, n) return max(money1,money2) nums = [2, 3, 2] print(Solution().rob(nums)) nums = [1, 2, 3, 1] print(Solution().rob(nums)) nums = [1, 2, 3] print(Solution().rob(nums))

中くらい

パイソン

関連記事