subject 1—— Home robbery

You are an experienced thief , Ready to steal a row of rooms along the street , Each room has a certain amount of cash , To prevent detection , You can't steal two neighboring houses , That is, if you steal the first , You can't steal a second house ; If you steal a second house , Then you can't steal the first and third .
Given an array of integers nums, The elements in the array represent the cash balance in each room , Please calculate the maximum amount of theft without being found .

Example
Input ：[1,2,3,4]
Output ：6( The best solution is to steal the second 2、4 A room )

Their thinking

 The common ground between greedy algorithm and dynamic programming is ： Both have optimal substructure properties , That is, the optimal solution of the problem includes the optimal solution of the subproblem .
 The difference between the two is ：
 In dynamic programming , The choice made in each step often depends on the solution of the relevant sub problem , Therefore, only when solving the relevant sub problems can we make a choice .
 In the greedy algorithm , Make the best choice only in the current state , Then we can solve the sub problem after making this choice .

If you use greedy algorithm to steal money , To steal more money , May give up two consecutive not to steal , Therefore, this method is not feasible , Consider using dynamic programming to solve . For every family , You can choose to steal or not , The equation of state transfer is dp[i] = Math.max(dp[i-1], dp[i-2]+nums[i-1).

Code implementation

import java.util.*;
public class Solution {
    
    public int rob (int[] nums) {
    
        int n = nums.length;
        if(n == 1)
            return nums[0];
        int[] dp = new int[n+1];
        dp[1] = nums[0];
        for(int i=2;i<=n;i++){
    
            // When you steal the first i A room , You can choose to steal or not 
            // If you steal , Then accumulate the last income , Otherwise, the accumulated income is the income of the superior 
            dp[i] = Math.max(dp[i-1],dp[i-2]+nums[i-1]);
        }
        return dp[n];
    }
}

subject 2—— House raiding II

You are an experienced thief , Ready to steal a row of rooms along the lake , Each room has a certain amount of cash , To prevent detection , You can't steal two neighboring houses , That is to steal the first , You can't steal a second house , If you steal a second house , Then you can't steal the first and third . The rooms along the lake form a closed circle , That is, the first room and the last room are considered adjacent .
Given a length of n Array of integers for nums, The elements in the array represent the amount of cash in each room , Please calculate the maximum amount of theft without being found .

Example
Input ：[1,3,6]
Output ：6(1 and 3 adjacent , Therefore, the best solution is to steal the second 3 A room )

Their thinking

Similar to topic one , But this question is circular , The first one is next to the last one , You can't get it at the same time , So it can be divided into two situations ： Steal the first one , Then the last one can't steal ; Steal the last one , Then the first one cannot steal . Aside from considering these , Others do the same as the first question .
Finally, take the largest value in the two cases .

Code implementation

import java.util.*;
public class Solution {
    
    public int rob (int[] nums) {
    
        int n = nums.length;
        if(n == 1)
            return nums[0];
        int[] dp = new int[n+1];
        // Steal the first one 
        dp[1] = nums[0];
        for(int i=2;i<n;i++){
    
            dp[i] = Math.max(dp[i-1], dp[i-2]+nums[i-1]);
        }
        int res = dp[n-1];
        Arrays.fill(dp,0);
        // Steal the last one 
        for(int i=2;i<=n;i++){
    
            dp[i] = Math.max(dp[i-1],dp[i-2]+nums[i-1]);
        }
        return Math.max(res,dp[n]);
    }
}