Re: [閒聊] 每日LeetCode已回收

看板Marginalman作者Rushia (みけねこ的鼻屎)時間3年前 (2022/12/14 10:08)推噓6(6推 0噓 0→)

留言6則, 6人參與討論串136/719 (看更多)

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