题解 | BM79 打家劫舍(二)

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param nums int整型一维数组
 * @return int整型
 */
function rob(nums) {
    // write code here
    let len = nums.length;
    if (len < 3) {
        return 0;
    } else if (len == 3) {
        let max = 0;
        for (let i = 0; i < 3; i++) {
            if (max < nums[i]) {
                max = nums[i];
            }
        }
        return max;
    } else {
        let ans = 0;
        let dp = Array.from(new Array(len + 1).fill(0));
        dp[1] = nums[0];
        for (let i = 2; i < len; i++) {
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i - 1]);
        }
        // 先得到偷第一家的最大值
        ans = dp[len - 1];
        dp[1] = 0;
        for (let i = 2; i <= len; i++) {
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i - 1]);
        }
        // 比较偷第一家的最大值和不偷第一家的最大值
        if (dp[len] > ans) {
            ans = dp[len];
        }
        return ans;
    }
}
module.exports = {
    rob: rob,
};