在做動態規劃類題目時最大的感覺就是能夠分析出這道題目需要用動態規劃演算法來解，卻沒有辦法構建出解題步驟，看到別人的分析時候又感覺代碼很簡單但是自己卻想不出，
其實這還是沒有理解到動態規劃演算法的基本思想，
這里我們通過一道例題來進行分析
由于相鄰房屋不能偷，如果我們從前往后思考當我們偷第一家那么我們就不能偷第二家，如果我們偷第二家我們就不能偷第三家…這時發現我們每走一步問題都為發生改變，
此時我們就應該換個角度思考從后往前看：
假如我們現在有5家房屋
當我們選擇偷第五家的時候，那么最大金額 = 第五家金額 + 前三家偷竊的最優解，
當我們不偷第五家的時候，那么最大金額 = 前四家偷竊的最優解，
這時候我們就能明白:如果只有一種情況時,最佳的選擇應該怎么做.然后根據這個最佳選擇往前一步推導,得到前一步的最佳選擇，
這道題最主要的部分就是要分析出每一步的最優解然后往后遞推，
我們來結合示例2進行分析：
輸入為：[2，7，9，3，1]
我們使用一個dp[]陣列儲存我們沒階段的最優解
(1)假設起始狀態下沒有房屋時最優解為：0
dp[0]=0(可以看作0房屋時候的最優解)
(2)如果只存在第一家的時候那么最優解為：2
dp[1]=2（1間房屋時候的最優解）
(3)如果存在兩家的時候最優解就是：7
dp[2]=7（2間房屋時候的最優解）
(4)如果存在三家的時候最優解就是：11
這里不難看出，當我們選擇偷第三家的時候：
最大金額 = dp[1]（前一家的最優解) + nums[2]（第三家的金額）
不偷第三家的時候：
最大金額 = dp[2] （前兩家的最優解）
然后我們比較這兩種情況，金額最大就作為前三家的最優解
即dp[3]=11（dp[1]+nums[2] > dp[2]）
(4)如果存在四家的時候最優解就是：11
dp[4]=11 （dp[2]+nums[3] < dp[3]）
(5)如果存在五家的時候最優解就是：12
dp[5]=12 （dp[3]+nums[4] > dp[4]）
所以我們經過分析后就能夠得出狀態轉移方程為：
dp[n] = MAX(dp[n-2] + nums[n-1], dp[n-1])
題解代碼：
class Solution {
public int rob(int[] nums) {
int len = nums.length;
if(len == 0){
return 0;
}
int[] dp = new int[len+1];
dp[0]=0;
dp[1]=nums[0];
for(int i=2; i<=len; i++){
dp[i] = Math.max(dp[i-2] + nums[i-1], dp[i-1]);
}
return dp[len];
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/46662.html
標籤：其他
下一篇：PAT乙級練習