当想不到今天要做什麽时就来解 LeetCode。
You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. All houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, adjacent houses have a security system connected, and it will automatically contact the police if two adjacent houses were broken into on the same night.
Given an integer array representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.nums
Example 1:
Input: nums = [2,3,2]
Output: 3
Explanation: You cannot rob house 1 (money = 2) and then rob house 3 (money = 2), because they are adjacent houses.
Example 2:
Input: nums = [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.
Example 3:
Input: nums = [1,2,3]
Output: 3
from typing import List
class Solution:
def solve(self, nums: List[int]) -> int:
bag = [0] * (len(nums))
bag[0] = nums[0]
bag[1] = max(nums[0], nums[1])
for i in range(2, len(nums)):
bag[i] = max(bag[i-2] + nums[i], bag[i-1])
print(bag)
return bag[-1]
pass
def rob(self, nums: List[int]) -> int:
if len(nums) <= 2:
return max(nums)
return self.solve(nums)
pass
一样是需要巧思才能快速解的动态规划题目。
这题的重点在於两个袋子,一个是昨天的一个是前天的,
要选择前天的+今天抢的,还是今天跳过这家用昨天的袋子呢...
本篇同步发文於个人网站: A First Set of Refactorings This arti...
终於来到了最後一章节,也算是蛮重要的「版本控制」 版本控制的好处是让你可以知道自己修改了什麽东西,方...
终於来到铁人赛最後一天了,30天说长不长说短也不短呢 一转眼30天就过了,这是我第一次参加铁人赛 我...
前言 由於 CKEditor 的客制化需要仰赖 Webpack,无法在 Vite 的专案上使用 因此...
本系列文之後也会置於个人网站 +--------+ +---------------+ | |--...