题解 | #打家劫舍(二)#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型一维数组 
     * @return int整型
     */
    public int rob (int[] nums) {
        // write code here
        int[] predp = new int[nums.length];
        int[] postdp = new int[nums.length];

        //该题目的最主要内容是构建两个dp
        //一个是0～n-1
        //一个是1～n
        //计算dp
        predp[1]= nums[0];
        for(int i=2;i<nums.length;i++){
            predp[i] = Math.max(predp[i-1],predp[i-2]+nums[i-1]);
        }

        postdp[1]= nums[1];
        for(int i=2;i<nums.length;i++){
            postdp[i] = Math.max(postdp[i-1],postdp[i-2]+nums[i]);
        }

        return Math.max(predp[nums.length-1],postdp[nums.length-1]);
    }
}

主要通过两个dp来搞定

0～n-1

1～n

计算这两个dp最大值

为什么要搞两个dp呢？因为收尾不能相连，中间需要空出来一个，要么是头空出来，要么是尾空出来