This is the 11th day of my participation in Gwen Challenge

Linear DP

Most DP problems, such as longest common subsequence, longest increasing subsequence, are actually linear DP. However, today’s example is not the classic DP questions, but to introduce some linear DP questions that often come up in the interview.

Example: Robbing

The title

【题目】 you are a professional thief who plans to rob the houses along the street. There is a certain amount of cash hidden in each room, and the only constraint on your ability to steal is that adjoining houses are equipped with an interconnected security system that alerts you if two houses are broken into on the same night. Given an array of non-negative integers representing the amount of money stored in each house, you are asked to calculate the maximum amount of money you can steal in one night without setting off the alarm.

Input: nums = [1,2,3,1]

Output: 4

Explanation: Steal NUMS [0] house (amount = 1), then steal NUMS [2] house (amount = 3). Maximum amount stolen = 1 + 3 = 4.

Next, we will follow DP’s 6-step analysis. . We slow down and analyze step by step.

1. Last step

For this problem, the last step is to deal with the n-1st room (let’s assume there are N rooms and we start at 0).

So the n-first room, I have two choices.

Steal: If you steal the n-1 room, the payoff is to steal the n-1 room after the first N-3 rooms.

Don’t steal: then only n-2 rooms need to be processed, so the benefit is the benefit after processing the first n-2 rooms.

2. The problem of child

There are unknowns in both of the options in the last step, which we can expand into subproblems:

What is the maximum benefit after processing [0… n-3]?

What is the maximum benefit after processing [0… N-2]?

Here we can unify the representation of the problem:

F (x) represents the highest return after processing [0… x] of these rooms.

3. Recursive relationships

After unifying the representation of the problem, let’s first express the last step:

f(N-1) = max(f(N-2), f(N-3) + nums[N-1])

I’m going to have to make a substitution here, and I’m going to replace N minus 1 with x. We can get:

f(x) = max(f(x-1), f(x-2) + nums[x])

4. Expression of F (x)

Here x represents the range of the original array [0… x]. Since all the interval represented by x starts at 0, there is no need to retain the information about the starting point of the interval, so only the endpoint x of the interval needs to be saved. We found that:

X is an integer;

The range of x is exactly the length of the NUMS array.

Although f(x) can be expressed as a hash, it is more direct and efficient to express the function mapping in an array. Therefore, we also express f(x) in dp[] arrays. And x is represented by the element I, which corresponds to the subscript of the NUMS array.

5. Initial conditions and boundaries

Initial conditions: First let’s look at the “uncomputable/out of bounds” case:

dp[0] = max(dp[0-1], dp[0-2] + nums[0]); // <-- out of bounds! dp[1] = max(dp[1-1], dp[1-2] + nums[1]); // <-- out of bounds! dp[2] = max(dp[2-1], dp[2-2] + nums[2]);Copy the code

We found that DP [0] and DP [1] would be out of bounds in the calculation process, so these two items need to be dealt with first.

Dp [0] : when only nums[0] can be stolen, it must be Max (0, nums[0]).

Beware of the trap that some questions may give you negative values. Do not write nums[0] directly.

Dp [1] : when there is room 0, room 1 can be stolen, because it cannot be stolen continuously, then only need to select the maximum value of 0, NUMs [0], nums[1] can be used. So dp[1] = Max (0, nums[0], nums[1]).

Bounds: Make sure you don’t cross array bounds!

6. Compute the order

Once you have the initial conditions and boundaries, you just need to take two more steps to know how to write the code. Next we begin to solve for dp[2], dp[3].

dp[2] = max(dp[2-1], dp[2-2] + nums[2]);
dp[3] = max(dp[3-1], dp[3-2] + nums[3]);
Copy the code

The complete code

Using the initial conditions and recursion we analyzed earlier, we can write the following code:

class Solution
{
  public int rob(int[] nums)
  {
    final int N = nums == null ? 0 : nums.length;
    if (N <= 0) {
      return 0;
    }
    int[] dp = new int[N];
    dp[0] = Math.max(0, nums[0]);
    if (N == 1) {
      return dp[0];
    }
    dp[1] = Math.max(0, Math.max(nums[0], nums[1]));
    for (int i = 2; i < N; i++) {
      dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
    }
    return dp[N - 1]; }}Copy the code

Complexity analysis: Time complexity O(N), space complexity O(N).

【 Summary 】 Through the six-step analysis, we quickly solved the classic DP problem.

deformation

There’s another little twist to this problem

The title

Title: You are a professional thief, planning to rob the houses along the street, each of which contains a certain amount of cash. All the houses in this place are in a circle, which means that the first house and the last house are right next to each other. At the same time, adjacent houses are equipped with an interconnected security system, if two adjacent houses are broken into on the same night, the system will automatically alarm. Given an array of non-negative integers representing the amount stored in each house, calculate the maximum amount you can steal without setting off the alarm.

Input: nums = [2,3,2]

Output: 3

Explanation: You cannot steal house NUMS [0] first (amount = 2) and then HOUSE NUMS [2] (amount = 2) because they are adjacent. The maximum gain is to steal nums[1]=3.

The complete code

class Solution {
    [b,e] [b,e] [b,e
    private int robHouse(int[] A, int b, int e) {
        if (b >= e) {
            return 0;
        }

        // dp[I] represents the maximum return from the range [b... I]
        int[] dp = new int[e];
        dp[b] = Math.max(0, A[b]);

        // If there is only one element
        if (e - b == 1) {
            return dp[b];
        }

        dp[b+1] = Math.max(0, Math.max(A[b], A[b+1]));

        for (int i = b + 2; i < e; i++) {
            dp[i] = Math.max(dp[i-1], dp[i-2] + A[i]);
        }

        return dp[e-1];
    }

    public int rob(int[] A) {
        // Since the houses here are end to end, so
        // We need to consider two cases,
        // A[0] does not grab: [1...N]
        // - A[0] = 2... n-1
        // Then the original array is actually two arrays

        // Handle special cases first
        if (A == null || A.length == 0) {
            return 0;
        }

        return Math.max(robHouse(A, 1, A.length),
                        A[0] + robHouse(A, 2, A.length - 1)); }}Copy the code

I’m just going to specifically deal with the value at zero, and I’m going to split the array into two parts.