Dynamic programming to solve the problem of looting

Dynamic programming solves the problem of looting

1. raid homes and plunder houses

Title Description

You are a professional thief , Plan to steal houses along the street . There is a certain amount of cash in every room , The only restriction on your theft is that adjacent houses are equipped with interconnected anti-theft systems , If two adjacent houses are broken into by thieves on the same night , The system will automatically alarm .
Given an array of non negative integers representing the storage amount of each house , Count you ** Without triggering the alarm **, The maximum amount that can be stolen overnight .

requirement

Example 1：

 Input ：[1,2,3,1]
 Output ：4
 explain ： Steal  1  House No  ( amount of money  = 1) , And then steal  3  House No  ( amount of money  = 3).
      Maximum amount stolen  = 1 + 3 = 4 .

Example 2：

 Input ：[2,7,9,3,1]
 Output ：12
 explain ： Steal  1  House No  ( amount of money  = 2),  Steal  3  House No  ( amount of money  = 9), Then steal  5  House No  ( amount of money  = 1).
      Maximum amount stolen  = 2 + 9 + 1 = 12 .

Force link ：https://leetcode.cn/problems/house-robber

Ideas

First consider the simplest case . If there is only one house , Then steal the house , You can steal up to the maximum total amount . If there are only two houses , Because the two houses are adjacent , You can't steal at the same time , Only one of the houses can be stolen , Therefore, choose the house with higher amount to steal , You can steal up to the maximum total amount .

If the number of houses is more than two , How to calculate the maximum total amount that can be stolen ？ For the first k（k>2） A house , There are two options ：

1. Theft section k A house , Then you can't steal k−1 A house , The total amount of theft is before k−2 The maximum total amount of a house is the same as that of k The sum of the amount of each house .
2. Don't steal k A house , The total amount of theft is before k−1 The maximum total amount of a house .

Choose the option with a larger total amount of theft from the two options , The total amount of theft corresponding to this option is the previous k The maximum total amount that can be stolen from a house .

use _dp_[_i_] Before presentation i The maximum total amount that can be stolen from a house , Then there is the following state transition equation ：
dp[i] = max(dp[i − 2] + nums[i], dp[i − 1])

Code

/** * @param {number[]} nums * @return {number} */
var rob = function(nums) {
    
  const length = nums.length;
  if (length === 1) return nums[0];
  const dp = Array(length).fill(0);
  dp[0] = nums[0];
  dp[1] = Math.max(nums[0], nums[1]);
  for(let i = 2; i < length; i++) {
    
    dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
  }
  return dp[length - 1];
};

The above method uses an array to store the results . Considering that the maximum total amount of each house is only related to the maximum total amount of the first two houses of the house , So you can use a scrolling array , Only the maximum total amount of the first two houses needs to be stored at each time .

/** * @param {number[]} nums * @return {number} */
var rob = function(nums) {
    
  let [dp1, dp2, dp] = [0, 0, 0];
  for(let i = 0; i < nums.length; i++) {
    
    dp = Math.max(dp1 + nums[i], dp2);
    dp1 = dp2;
    dp2 = dp;
  }
  return dp;
};

2. raid homes and plunder houses II

Title Description

You are a professional thief , Plan to steal houses along the street , There is a certain amount of cash in every room . All the houses in this place are Make a circle , This means that the first house and the last house are next to each other . meanwhile , Adjacent houses are equipped with interconnected anti-theft system , If two adjacent houses are broken into by thieves on the same night , The system will automatically alarm .

Given an array of non negative integers representing the storage amount of each house , Count you Without triggering the alarm device , The maximum amount you can steal tonight .

requirement

Example 1：

 Input ：nums = [2,3,2]
 Output ：3
 explain ： You can't steal first  1  House No （ amount of money  = 2）, And then steal  3  House No （ amount of money  = 2）,  Because they are next to each other .

Example 2：

 Input ：nums = [1,2,3,1]
 Output ：4
 explain ： You can steal first  1  House No （ amount of money  = 1）, And then steal  3  House No （ amount of money  = 3）.
      Maximum amount stolen  = 1 + 3 = 4 .

Example 3：

 Input ：nums = [1,2,3]
 Output ：3

Force link ：https://leetcode.cn/problems/house-robber-ii

Ideas

First consider the simplest case . If there is only one house , Then steal the house , You can steal up to the maximum total amount . If there are only two houses , Because the two houses are adjacent , You can't steal at the same time , Only one of the houses can be stolen , Therefore, choose the house with higher amount to steal , You can steal up to the maximum total amount .

Note that when the number of houses does not exceed two , You can only steal one house at most , Therefore, there is no need to consider the end-to-end problem . If the number of houses is more than two , You have to think about the end-to-end problem , The first house and the last house cannot be stolen at the same time .

How can we ensure that the first house and the last house are not stolen at the same time ？ If you steal the first house , You can't steal the last house , Therefore, the scope of house theft is from the first house to the last second house ; If you steal the last house , You can't steal the first house , Therefore, the scope of house theft is from the second house to the last house .

Hypothetical array nums The length of is n. If you don't steal the last house , The subscript range of the stolen house is [0, n - 2]; If you don't steal the first house , The subscript range of the stolen house is [1,n − 1]. After determining the subscript range of the stolen house , That is to say, it can be solved by the method of the above question . For two subscript ranges, calculate the maximum total amount that can be stolen , The maximum value is at n The maximum total amount that can be stolen from a house .

Suppose the subscript range of the stolen house is [start, end], use dp[i] Indicates in the subscript range [start, i] The maximum total amount that can be stolen in the , Then there is the following state transition equation ：
dp[i] = max(dp[i − 2] + nums[i], dp[i − 1])
Considering that the maximum total amount of each house is only related to the maximum total amount of the first two houses of the house , So you can use a scrolling array , Only the maximum total amount of the first two houses needs to be stored at each time , Reduce the space complexity to O(1).

Code

/** * @param {number[]} nums * @return {number} */
var rob = function(nums) {
    
  if (nums.length === 1) return nums[0];
  return Math.max(robRange(0, nums.length - 1), robRange(1, nums.length));
  function robRange(start, end) {
    
    let [dp1, dp2, dp] = [0, 0, 0];
    for(let i = start; i < end; i++) {
    
      dp = Math.max(dp1 + nums[i], dp2);
      dp1 = dp2;
      dp2 = dp;
    }
    return dp;
  }
};

3. raid homes and plunder houses III

Title Description

The thief found a new area to steal . There is only one entrance to the area , We call it root.

except root outside , Each house has and only has one “ Father ” The house is connected to it . After some reconnaissance , The clever thief realized that “ All the houses in this place are arranged like a binary tree ”. If Two directly connected houses were robbed the same night , The house will alarm automatically .

Given a binary tree root . return Without triggering the alarm , The maximum amount a thief can steal .

requirement

Example 1:

 Input : root = [3,2,3,null,3,null,1]
 Output : 7 
 explain :  The maximum amount a thief can steal in a night  3 + 3 + 1 = 7

Example 2:

 Input : root = [3,4,5,1,3,null,1]
 Output : 9
 explain :  The maximum amount a thief can steal in a night  4 + 5 = 9

Force link ：https://leetcode.cn/problems/house-robber-iii

Ideas

This topic itself is a tree version of dynamic programming , Through this question , Can understand the tree problem in the dynamic programming problem solution , We solve the problem step by step through two methods .

• Solution 1 is realized by recursion , Although the problem has been solved , But the complexity is too high
• Solution 2 solves the repeated subproblem in method 1 , The performance has been improved a hundred times

Solution 1 、 Recurrence of violence - Optimal substructure
We use grandpa 、 Two children 、4 A grandson to illustrate the problem . First, define the state of the problem

• First, make it clear that adjacent nodes cannot steal , That is, Grandpa chose to steal , The son can't steal , But grandson can steal
• The binary tree has only two children , One grandpa is the most 2 A son ,4 A grandson

According to the above conditions , We can figure out how to calculate the money of a single node
4 Money stolen by a grandson + Grandpa's money VS Money stolen by two sons Which combination has more money , The maximum amount of money that the current node can steal . This is the optimal substructure in dynamic programming
Because it's a binary tree , Here you can choose to calculate all child nodes
4 The money invested by my grandson and grandpa is as follows ：
method1 = root.val + rob(root.left.left) + rob(root.left.right) + rob(root.right.left) + rob(root.right.right);
The two sons stole the following money ：
method2 = rob(root.left) + rob(root.right);
Choosing a scheme with a large amount of money is
result = Math.max(method1, method2);
Write the above scheme into the following code ：

/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */
/** * @param {TreeNode} root * @return {number} */
var rob = function(root) {
    
  if (!root) return 0;
  let money = root.val;
  if (root.left) {
    
    money += (rob(root.left.left) + rob(root.left.right));
  }
  if (root.right) {
    
    money += (rob(root.right.left) + rob(root.right.right));
  }
  return Math.max(money, rob(root.left) + rob(root.right));
};

Solution 2 、 Memorize - Solve the repeated subproblem
For solving a problem that is too slow , After analyzing its implementation , We found out that grandpa was calculating how much money he could steal , At the same time, we calculate 4 How much money can a grandson steal , Also calculated 2 How much money can a son steal . So when my son is a grandfather , It will cause repeated calculation of grandchildren .
So we found a key optimization point of dynamic programming
Repeat the question
In this step, we optimize the repeated subproblem , When we were doing Fibonacci series , The optimization scheme used is memorization , But the previous problems were solved by using arrays , Save the results of each calculation , Next time, if we calculate , Take... From the cache , No more calculations , This ensures that each number is calculated only once .
Because binary tree is not suitable for using array as cache , This time we use a hash table to store the results ,TreeNode treat as key, The money you can steal is used as value
The code after solution 1 plus memory optimization is as follows ：

/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */
/** * @param {TreeNode} root * @return {number} */
var rob = function(root) {
    
  const memo = new Map();
  return robInternal(root);

  function robInternal (root) {
    
    if (!root) return 0;
    if (memo.has(root)) return memo.get(root);
    let money = root.val;

    if (root.left) {
    
      money += (robInternal(root.left.left) + robInternal(root.left.right));
    }
    if (root.right) {
    
      money += (robInternal(root.right.left) + robInternal(root.right.right));
    }
    const result = Math.max(money, robInternal(root.left) + robInternal(root.right));
    memo.set(root, result);
    return result;
  }
};