打家劫舍

1 打家劫舍

• 题目
  你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
• 思路
  1）子问题：原来的问题是“从全部房子中能偷到的最大金额”，将问题的规模缩小，子问题就是“从 k个房子中能偷到的最大金额”，用 f(k)表示。
  2）子问题的递推关系：
  有n个房子，每个房子的金额分别是nums[0]、nums[1]、…、nums[n-1]，
  子问题就是“从 k个房子中能偷到的最大金额”f（k）。
  有两种偷法：一是偷第k个房子nums[k-1]，那么问题就变成在前 k-2个房子中偷到的最大的金额。二是不偷第k个房子，问题就变成在前 k-1个房子中偷到最大的金额，也就是子问题f(k−1)。两种方法选择金额较大的一种结果。
  
  递推关系是：f（k）=max（f（k-2）+nums[k-1]，f（k-1））//数组下标从0开始
  找出边界：第0个房子时，f（0）=0；第一个房子时f（1）=nums[0]
  3）找出计算顺序：（代码的实现）只需要按 k 从小到大依次计算子问题即可。
  4）空间优化
  
  修改：

let preTwo=nums[0]
let preOne=Math.max(nums[1],nums[0])

• 代码

//动态规划
function rob_2(nums) {
    if(nums.length <= 0){
        return false;
    }
    let result; //保存结果
    let preTwo = 0;  //用来表示当前房间往前第二个房间时的最优解，初始化为第0间金额为0
    let preOne = nums[0];  //用来表示当前房间往前第二个房间时的最优解，初始化为第0间金额为nums[0]
    if(nums.length === 1){
        result = nums[0];
    }
    //自di向上循环数组
    for(let i= 1; i < nums.length; i++){
        result = Math.max(preTwo + nums[i], preOne);
        preTwo = preOne;
        preOne = result;
    }
    return result;
}
//奇偶数的动态规划
let rob = function(nums) {
    if(nums.length <= 0){
        return false;
    }
    let result; //保存将要返回的结果
    let sum = [0, 0];//数组的第一个数保存奇数的和，第二保存偶数的和
    if(nums.length === 1){
        result = nums[0];
    }
    for(let i = 0; i < nums.length; i++){
        if(i % 2 === 0){
            //奇数时求和
            sum[0] +=nums[i];
            sum[0] = Math.max(sum[0], sum[1]);
        }
        if(i % 2 !== 0){
            //偶数求和
            sum[1] +=nums[i];
            sum[1] = Math.max(sum[0], sum[1]);
        }
    }
    result = Math.max(sum[0], sum[1]);
    return result;
};