傳送門:198. 打家劫舍>
比較經典的dp,找到狀態轉移方程dp[i] = max(dp[i-2]+num[i],dp[i-1])
如果兩間相鄰的房屋在同一晚上被小偷闖入，系統會自動報警,即相鄰的數字不能同時作為最終求和的有效數字
把這個問題拆分成子問題即從 k 個房子中能偷到的最大金額
第k個房子的最大金額則考慮如果不偷這個房子,那么問題變成前k-1個房子所偷到的最大金額,如果偷這個房子,那么前一個房子顯然不能偷,其他房子不受影響,則考慮這個房子+k-2個房子的金額
所以得出dp方程為:
dp[i] = max(dp[i-2]+num[i],dp[i-1])
邊界情況為dp[0] = num[0];
dp[1 ] = Math.max(num[0],num[1])
class Solution {
public int rob(int[] nums) {
if(nums.length == 0){
return 0;
}
if(nums.length == 1){
return nums[0];
}
int[] dp = new int[nums.length];
dp[0] = nums[0];
dp[1] = Math.max(nums[0],nums[1]);
for (int i = 2; i < nums.length; i++) {
dp[i] = Math.max(dp[i-1],nums[i]+dp[i-2]);
}
return dp[nums.length-1];
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/245755.html
標籤：其他
上一篇：用JAVA撰寫24點小游戲