213. 打家劫舍 II(leetcode)

https://leetcode.cn/problems/house-robber-ii/description/

灵神题解:

https://leetcode.cn/problems/house-robber-ii/solutions/2445622/jian-ji-xie-fa-zhi-jie-diao-yong-198-ti-qhvri/

class Solution {
    public int rob(int[] nums) {
        // f[i]表示前i个房屋选能获得的最大金额
        // 以第i个房屋选还是不选划分子集,由于是环状,因此选第i个房屋,则需要考虑i-1,i+1都不能选择
        // 这里无法处理i+1,只能分为选或者不选第一个房屋的情况,
        // 1.不选择第一个房屋的情况,则最后一个房屋可以选择,i可以等于nums.length-1
        // 2.选择第一个房屋的情况,最后一个房屋不能选择 , i<nums.length-1
        // 状态方程一样,但是初值不同,
        // f[i]=max(f[i-2]+nums[i],f[i-1])
        // 1.f[1]=nums[0],2.f[1]=0 这里f[1]和上面状态方程的下标有偏移一位
        int N = 110;
        int[] f=new int[N];
        f[1]=nums[0];
        int res=0;
        for(int i=2;i<=nums.length-1;i++)
        {
            f[i]=Math.max(f[i-2]+nums[i-1],f[i-1]);
            res=Math.max(res,f[i]);
        }
        Arrays.fill(f,0);
        f[1]=0; // 可以省略,但是为了表述清楚,保留
        for(int i=2;i<=nums.length;i++)
        {
            f[i]=Math.max(f[i-2]+nums[i-1],f[i-1]);
            res=Math.max(res,f[i]);
        }
        return res;
    }
}