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

如何思考环形问题？

• 对于每一家，可以选择偷或者不偷，然后比较这两个情况的最大值得出可以盗取的最大金额：max(dp[i-1], nums[i] + (i-2 >= 0 ? dp[i-2] : 0))
• 由于环形问题，第一家和最后一家不能同时取到，因此要分两种情况设置两种情况的dp数组：
• 只偷第一家不偷最后一家，此时dp[0]设置为第一家的金额，并且dp数组的结束位置在倒数第二家，表示不偷最后一家
• 只偷最后一家不偷第一家，此时dp[0]设置为0，表示不偷第一家，dp数组结束在最后一家
• 比较上述两种情况的最大值则可以得到可以盗取的最大金额，由于第一种情况结束位置为倒数第二家，所以第一种情况的最大金额为dp[nums.length-2]，第二种情况结束在最后一家，最大金额为dp[nums.length-1]

参考

https://blog.nowcoder.net/n/0d5c70d8a03d417480331a3700e2900a?f=comment

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型一维数组 
     * @return int整型
     */
    public int rob (int[] nums) {
        // write code here
        // dp数组表示偷第i家时的最大金额
        // 环形问题，有多个情况，设置多个dp数组
        int[] dpFirst = new int[nums.length];  // 偷第一家，不偷最后一家
        int[] dpLast = new int[nums.length];  // 偷最后一家，不偷第一家

        // 最小子问题
	    // 没有考虑只有一家或者0家的情况，此时直接给第一个索引或第二个索引赋值会出错。
        dpFirst[0] = nums[0];  // 从第一家开始偷，第一家初始金额为nums[0]
        dpLast[1] = nums[1];  // 从第二家开始偷，可以偷最后一家
	    // dpFirst[1] = Math.max(nums[0], nums[1]); 还要处理这一步

        for (int i = 2; i < nums.length; ++i) {
            // 对于每一家，可以选择偷或者不偷
            dpFirst[i] = Math.max(dpFirst[i-1], nums[i] + dpFirst[i-2]);
            dpLast[i] =  Math.max(dpLast[i-1], nums[i] + dpLast[i-2]);
        }

        return Math.max(dpFirst[nums.length-2], dpLast[nums.length-1]);
    }
}

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param nums int整型一维数组 
 * @return int整型
 */
function rob( nums ) {
    // write code here
    const dpFirst = new Array(nums.length).fill(0);  // 偷第一家，不偷最后一家
    const dpLast = new Array(nums.length).fill(0);  // 偷最后一家，不偷第一家
    dpFirst[0] = nums[0];
    dpLast[0] = 0;

    for (let i = 1; i < nums.length; ++i) {
        if (i === 1) {
            dpFirst[1] = Math.max(nums[0], nums[1]);
            dpLast[1] = nums[1];
        }
        else {
            dpFirst[i] = Math.max(dpFirst[i-1], nums[i] + (i-2 >= 0 ? dpFirst[i-2] : 0));  // 对于每一家，可以选择偷和不偷
            dpLast[i] = Math.max(dpLast[i-1], nums[i] + (i-2 >= 0 ? dpLast[i-2] : 0));  // 对于每一家，可以选择偷和不偷
        }
    }


    return Math.max(dpFirst[nums.length-2], dpLast[nums.length-1]);
}
module.exports = {
    rob : rob
};