House Robber :
你是一名專業的強盜,計劃搶劫沿街的房屋。 每棟房子都藏有一定數量的金錢,唯一阻止你搶劫的限制是相鄰的房子都連接了安全系統,如果在同一晚兩間相鄰的房子被闖入,它會自動聯繫警察。
給定一個代表每所房子金額的非負整數列表,確定你今晚可以在不報警的情況下搶劫的最大金額。
每個房間裡有些價值的物品,不能偷連續的房間,那麼求最多能偷多少物品?
Python
解法 :
偷第i間就不能偷第i-1間,所以rob[i]=nums[i] + rob[i-2](第i-2間的值加上偷了第i間的值)
不偷第i間,則rob[i] = rob[i-1],因為沒偷第i間
兩個比較選最大的 : rob[i] = max(nums[i] + rob[i-2], rob[i-1])
class Solution:
def rob(self, nums: List[int]) -> int:
l = len(nums)
if l == 0:
return 0
if l == 1:
return nums[0]
rob = [0] * l
rob[0] = nums[0] #第一間
rob[1] = max(nums[0], nums[1]) #兩間選一間偷
for i in range(2, l):
rob[i] = max(nums[i] + rob[i-2], rob[i-1])
return rob[-1]
C++
class Solution {
public:
int rob(vector<int>& nums) {
int n = nums.size();
if (n == 0) {
return 0;
} else if (n == 1) {
return nums[0];
} else if (n == 2) {
return max(nums[0], nums[1]);
}
vector<int> dp(n);
dp[0] = nums[0];
dp[1] = max(nums[0], nums[1]);
for (int i = 2; i < n; i++) {
dp[i] = max(dp[i-1], dp[i-2] + nums[i]);
}
return dp[n-1];
}
};