讨论/《动态规划精讲(一)》 - 打家劫舍 II/
《动态规划精讲(一)》 - 打家劫舍 II

Java版本,爷爷奶奶都看得懂~~

class Solution {
    public int rob(int[] nums) {
        int len=nums.length;
        if (len==1)return nums[0];//只有1家人
        if (len==2)return Math.max(nums[0],nums[1]);//只有2家人
        int[][][]dp=new int[len][2][2];
        dp[0][1][1]=nums[0];//dp[家数][偷和不偷两个状态][第一家偷和不偷两种状态]
        for (int i = 1; i < len-1; i++) {//注意,迭代到lenl-2,len-1情况要专门处理
            // 不偷第1家情况
            dp[i][0][0]=Math.max(dp[i-1][0][0],dp[i-1][1][0]);
            dp[i][1][0]=dp[i-1][0][0] + nums[i];

            // 偷第1家情况
            dp[i][0][1]=Math.max(dp[i-1][0][1],dp[i-1][1][1]);
            dp[i][1][1]=dp[i-1][0][1] + nums[i];
        }
        // 开始处理环形的最后一家,是否偷最后一家和第1家状态有关:
        //情况1:如果偷过第1家,那么最后一家肯定不能偷,只能从倒数第二家状态选择最大值;
        //情况2:如果没有偷过第1家,那么最后一家可偷可不偷,有两种选择,从倒数第二家状态转移过来;

        // 第1家没偷的两种情况
        dp[len-1][0][0]=Math.max(dp[len-2][0][0],dp[len-2][1][0]);
        dp[len-1][1][0]=dp[len-2][0][0]+nums[len-1];

        // 偷了第1家唯一一种情况
        dp[len-1][0][1]=Math.max(dp[len-2][0][1],dp[len-2][1][1]);
        
        // 注意,要返回最大值!这里由于dp[len-1][1][1]是非法的,故只从三种情况中选择最大值
        return Math.max(Math.max(dp[len-1][0][0],dp[len-1][0][1]),dp[len-1][1][0]);
    }
}
展开全部 8 讨论