讨论/技术交流/双百的打家劫舍AWSL/

image.png
啊!!没想到啊,我也能不参考别人写出打家劫舍的动态规划问题,开心~

class Solution {
    public int rob(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        int len = nums.length;
        if (len == 1) return nums[0];
        int[] dpTable = new int[len];
        //从最后1家偷起
        dpTable[len - 1] = nums[len - 1];
        //从最后第2家偷起
        dpTable[len - 2] = nums[len - 2];
        //max为最后2家的最大值和最后1家的最大值 ...最后k+1家的最大值和最后k家的最大值
        int[] max = new int[]{dpTable[len - 2] > dpTable[len - 1] ? dpTable[len - 2] : dpTable[len - 1], dpTable[len - 1]};
        for (int idx = len - 3; idx >= 0; idx--) {
            int k = (len - idx) % 2;
            dpTable[idx] = max[k] + nums[idx];
            if (dpTable[idx] > max[k]) {
                max[k] = dpTable[idx];
            }
            if(max[k]<max[(k+1)%2]){
                max[k] = max[(k + 1) % 2];
            }
        }
        return max[0] > max[1] ? max[0] : max[1];
    }

 
}

LeetCode 基础算法中有详细的评论解题过程,简要的记录了一下,打家看看就行。
[https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xnq4km/](LeetCode 基础算法-打家劫舍)

1
共 0 个回复
暂无回复