推 pandix: 大師 12/14 10:13
推 SecondRun: 好難 12/14 10:16
推 wwndbk: 大師 12/14 10:16
推 ririoshi: 大師 12/14 10:29
推 twosheep0603: 這題DP還滿直覺的 12/14 11:56
推 AyuniD: 看來這禮拜是 DP 週 12/14 20:45
198. House Robber
龍大是一個小偷，他跑到一條街上要偷一整排的家戶，但是家戶裝有警報系統所以
你如果偷了這個家他的左右兩邊的家都會知道，求出龍大要怎麼偷才能偷最多錢。
Example：
Input: nums = [2,7,9,3,1]
Output: 12
Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5
(money = 1).
Total amount you can rob = 2 + 9 + 1 = 12.
思路：
1.因為偷了i位置就不能偷i-1位置，所以我們只要紀錄不偷前一家和偷前一家哪一個
可以拿到更多錢就好，可以使用動態規劃來維護這個數值。
2.dp(i)表示在第i個家的時候可偷到的最多錢，狀態轉移方程：
dp(i) = max(dp(i-1), dp(i-2)+nums(i))
3.因為狀態轉移方程要往前找兩個，所以我們必須初始化dp(0)和dp(1)的數值，顯然的
dp(0)一定是nums[0]，而dp[1]會是max(nums[0], nums[1])，遇到長度小於2的case
則直接返回唯一的元素。
Java Code：
-----------------------------
class Solution {
public int rob(int[] nums) {
int n = nums.length;
if (n == 1) {
return nums[0];
}
int[] dp = new int[n];
dp[0] = nums[0];
dp[1] = Math.max(nums[0], nums[1]);
for (int i = 2; i < n; i++) {
dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
}
return dp[n - 1];
}
}
-----------------------------
--
https://i.imgur.com/3e5CZfj.jpg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.160.89.30 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1670983698.A.AB4.html