LeetCode动态规划

198.打家劫舍

题目描述：你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你不触动警报装置的情况下，一夜之内能够偷窃到的最高金额。

思路分析：

动态规划方程：dp[n] = MAX( dp[n-1], dp[n-2] + num )
由于不可以在相邻的房屋闯入，所以在当前位置 n 房屋可盗窃的最大值，要么就是 n-1 - 房屋可盗窃的最大值，要么就是 n-2 房屋可盗窃的最大值加上当前房屋的值，二者之间取最大值
举例来说：1 号房间可盗窃最大值为 33 即为 dp[1]=3，2 号房间可盗窃最大值为 44 即为 dp[2]=4，3 号房间自身的值为 22 即为 num=2，那么 dp[3] = MAX( dp[2], dp[1] + num ) = MAX(4, 3+2) = 5，3 号房间可盗窃最大值为 5
时间复杂度：O(n)O(n)，nn 为数组长度

var rob = function(nums) {
    let len = nums.length;
    if (len === 0) return 0;
    let dp = [];
    dp[0] = nums[0];
    dp[1] = Math.max(nums[0],nums[1]);
    for (let i = 2; i < len; i++) {
        dp[i] = Math.max(dp[i-1],dp[i-2]+nums[i]);
    }
    return dp[len-1];
};

213.打家劫舍II

题目描述：你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。
思路分析：
本题为上一题的加强版，可以分为两种情况：

偷第一家，则不投最后一家
不偷第一家，则偷最后一家
将两张情况的切片数组代入到上一题的函数里，求得两个结果取最大值即可。

var rob = function(nums) {
    if (nums.length === 0) return 0;
    if (nums.length === 1) return nums[0];
    return Math.max(DP(nums.slice(1)), DP(nums.slice(0,nums.length-1)));
    //198题打家劫舍的函数
    function DP(nums) {
        let len = nums.length;
        if (len === 0) return 0;
        let dp = [];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0],nums[1]);
        for (let i = 2; i < len; i++) {
            dp[i] = Math.max(dp[i-1],dp[i-2]+nums[i]);
        }
        return dp[len-1];
    }
};

337.打家劫舍III

题目描述：在上次打劫完一条街道之后和一圈房屋后，小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为“根”。除了“根”之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。
计算在不触动警报的情况下，小偷一晚能够盗取的最高金额。
思路分析：
打不打劫根节点，会影响打劫一棵树的收益：

打劫根节点，则不能打劫左右子节点，但是能打劫左右子节点的四个子树。
不打劫根节点，则能打劫左子节点和右子节点，收益是打劫左右子树的收益之和。
因此可以递归计算。

const rob = (root) => { // 打劫以root为根节点的子树的最大收益
  if (root == null) return 0;
  // 打劫包括根节点的收益，保底是root.val
  let robIncludeRoot = root.val; 
  if (root.left) {
    robIncludeRoot += rob(root.left.left) + rob(root.left.right);
  }
  if (root.right) {
    robIncludeRoot += rob(root.right.left) + rob(root.right.right);
  }
  // 打劫不包括根节点的收益
  const robExcludeRoot = rob(root.left) + rob(root.right); 
  // 二者取其大
  return Math.max(robIncludeRoot, robExcludeRoot); 
};

但是注意，我们计算了 root 的四个孙子子树，又计算了 root 的左右子树，而后者会把 root 的孙子子树重复计算一遍。我们把计算过的结果存到 map。下次遇到相同的子问题时直接拿过来用，不用做重复的递归。这就是动态规划——记忆化递归。

const rob = (root) => {
  const memo = new Map();
  return helper(root);

  const helper = (root) => {
    if (root == null) return 0;
    // memo中有缓存的结果，直接返回它
    if (memo.has(root)) return memo.get(root);

    let robIncludeRoot = root.val;
    if (root.left) {
      robIncludeRoot += helper(root.left.left) + helper(root.left.right);
    }
    if (root.right) {
      robIncludeRoot += helper(root.right.left) + helper(root.right.right);
    }

    const robExcludeRoot = helper(root.left) + helper(root.right);

    const res = Math.max(robIncludeRoot, robExcludeRoot);
    // 保存当前子树的计算结果
    memo.set(root, res);
    return res;
  };
};

连续子数组的最大值

输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。

动态规划

var maxSubArray = function(nums) {
    let temp = nums[0];
    let max = nums[0];
    for (let i = 1; i < nums.length; i++) {
        if (temp > 0) {
            temp = temp + nums[i];
        } else {
            temp = nums[i];
        }
        max = Math.max(temp, max);
    }
    return max;
};