→ ILoveErr: 大師 01/21 15:21
https://leetcode.com/problems/house-robber/description
198. House Robber
給你一個陣列 nums，nums[i] 表示第 i 家有多少錢，小偷要從這些家偷錢，如果他偷了
第 i 家，他就不能偷相鄰的家，求出怎麼偷可以偷到最多錢。
思路：
1.拿或不拿的問題基本上就是動態規劃，分成拿當前或不拿，取大的，
若 f(i) 表示到第 i 個位置可以偷到的最大金錢，狀態轉移方程：
f(i) = MAX(f(i - 1), f(i - 2) + nums[i])
2.因為只需要前兩個狀態所以可以把dp陣列壓一壓，空間複雜度O(1)。
Java Code：
--------------------------------------
class Solution {
public int rob(int[] nums) {
int one = nums[0];
int two = 0;
for (int i = 1; i < nums.length; i++) {
int max = Math.max(one, two + nums[i]);
two = one;
one = max;
}
return Math.max(one, two);
}
}
--------------------------------------
--
https://i.imgur.com/DANRJFR.jpg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 122.100.73.13 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1705821477.A.013.html
※ 編輯: Rushia (122.100.73.13 臺灣), 01/21/2024 15:19:00