LeetCode動(dòng)態(tài)規(guī)劃

198.打家劫舍

題目描述：你是一個(gè)專業(yè)的小偷析苫，計(jì)劃偷竊沿街的房屋衩侥。每間房內(nèi)都藏有一定的現(xiàn)金，影響你偷竊的唯一制約因素就是相鄰的房屋裝有相互連通的防盜系統(tǒng)茫死，如果兩間相鄰的房屋在同一晚上被小偷闖入，系統(tǒng)會(huì)自動(dòng)報(bào)警峦萎。
給定一個(gè)代表每個(gè)房屋存放金額的非負(fù)整數(shù)數(shù)組屡久，計(jì)算你不觸動(dòng)警報(bào)裝置的情況下骨杂，一夜之內(nèi)能夠偷竊到的最高金額。

思路分析：

動(dòng)態(tài)規(guī)劃方程：dp[n] = MAX( dp[n-1], dp[n-2] + num )
由于不可以在相鄰的房屋闖入搓蚪，所以在當(dāng)前位置 n 房屋可盜竊的最大值丁鹉，要么就是 n-1 - 房屋可盜竊的最大值，要么就是 n-2 房屋可盜竊的最大值加上當(dāng)前房屋的值揣钦，二者之間取最大值
舉例來說：1 號(hào)房間可盜竊最大值為 33 即為 dp[1]=3，2 號(hào)房間可盜竊最大值為 44 即為 dp[2]=4冯凹，3 號(hào)房間自身的值為 22 即為 num=2，那么 dp[3] = MAX( dp[2], dp[1] + num ) = MAX(4, 3+2) = 5宇姚，3 號(hào)房間可盜竊最大值為 5
時(shí)間復(fù)雜度：O(n)O(n)，nn 為數(shù)組長度

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

題目描述：你是一個(gè)專業(yè)的小偷阱持，計(jì)劃偷竊沿街的房屋，每間房內(nèi)都藏有一定的現(xiàn)金衷咽。這個(gè)地方所有的房屋都圍成一圈，這意味著第一個(gè)房屋和最后一個(gè)房屋是緊挨著的蒜绽。同時(shí)，相鄰的房屋裝有相互連通的防盜系統(tǒng)躲雅，如果兩間相鄰的房屋在同一晚上被小偷闖入，系統(tǒng)會(huì)自動(dòng)報(bào)警此蜈。
給定一個(gè)代表每個(gè)房屋存放金額的非負(fù)整數(shù)數(shù)組，計(jì)算你在不觸動(dòng)警報(bào)裝置的情況下裆赵，能夠偷竊到的最高金額。
思路分析：
本題為上一題的加強(qiáng)版战授，可以分為兩種情況：

偷第一家页藻，則不投最后一家
不偷第一家植兰，則偷最后一家
將兩張情況的切片數(shù)組代入到上一題的函數(shù)里，求得兩個(gè)結(jié)果取最大值即可楣导。

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題打家劫舍的函數(shù)
    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

題目描述：在上次打劫完一條街道之后和一圈房屋后，小偷又發(fā)現(xiàn)了一個(gè)新的可行竊的地區(qū)噩凹。這個(gè)地區(qū)只有一個(gè)入口，我們稱之為“根”驮宴。除了“根”之外呕缭，每棟房子有且只有一個(gè)“父“房子與之相連堵泽。一番偵察之后迎罗，聰明的小偷意識(shí)到“這個(gè)地方的所有房屋的排列類似于一棵二叉樹”。如果兩個(gè)直接相連的房子在同一天晚上被打劫佳谦，房屋將自動(dòng)報(bào)警。
計(jì)算在不觸動(dòng)警報(bào)的情況下钻蔑，小偷一晚能夠盜取的最高金額。
思路分析：
打不打劫根節(jié)點(diǎn)咪笑，會(huì)影響打劫一棵樹的收益：

打劫根節(jié)點(diǎn)娄涩，則不能打劫左右子節(jié)點(diǎn)窗怒，但是能打劫左右子節(jié)點(diǎn)的四個(gè)子樹扬虚。
不打劫根節(jié)點(diǎn)，則能打劫左子節(jié)點(diǎn)和右子節(jié)點(diǎn)辜昵，收益是打劫左右子樹的收益之和。
因此可以遞歸計(jì)算堪置。

const rob = (root) => { // 打劫以root為根節(jié)點(diǎn)的子樹的最大收益
  if (root == null) return 0;
  // 打劫包括根節(jié)點(diǎn)的收益躬存，保底是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);
  }
  // 打劫不包括根節(jié)點(diǎn)的收益
  const robExcludeRoot = rob(root.left) + rob(root.right); 
  // 二者取其大
  return Math.max(robIncludeRoot, robExcludeRoot); 
};

但是注意舀锨，我們計(jì)算了 root 的四個(gè)孫子子樹，又計(jì)算了 root 的左右子樹盾剩，而后者會(huì)把 root 的孫子子樹重復(fù)計(jì)算一遍。我們把計(jì)算過的結(jié)果存到 map彪腔。下次遇到相同的子問題時(shí)直接拿過來用，不用做重復(fù)的遞歸。這就是動(dòng)態(tài)規(guī)劃——記憶化遞歸恭垦。

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

  const helper = (root) => {
    if (root == null) return 0;
    // memo中有緩存的結(jié)果，直接返回它
    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);
    // 保存當(dāng)前子樹的計(jì)算結(jié)果
    memo.set(root, res);
    return res;
  };
};

連續(xù)子數(shù)組的最大值

輸入一個(gè)整型數(shù)組番挺，數(shù)組中的一個(gè)或連續(xù)多個(gè)整數(shù)組成一個(gè)子數(shù)組。求所有子數(shù)組的和的最大值襟衰。

動(dòng)態(tài)規(guī)劃

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;
};