This is the NTH day of my participation in the August Wen Challenge.More challenges in August

Dynamic programming, DP for short; It is also very common in the algorithm questions in the interview, which is a common way to find the optimal solution. It has always been a problem that has bothered me before.

Common usage routines (step by step optimization)

① Recursion of violence (from top to bottom, overlapping subproblems occur)

② Memorized search (top-down)

③ Recursion (bottom-up)

Common steps of dynamic planning:

“Dynamic” in dynamic programming can be understood as “changing state”.

① Define the state (the state is the solution of the original problem, subproblem) for example, define the meaning of dp(I)

② Set the initial state (boundary), for example, set dp(0)

③ Determine the state transition equation for example, determine the relationship between DP (I) and DP (I – 1)

Meaning:

① Break down the complex original problem into several simple sub-problems

② Each subproblem is solved only once, and their solutions are saved

③ Finally, the solution of the original problem is deduced

Problems that can be solved by dynamic programming usually have two characteristics: optimal substructure (optimization principle) :

By solving the optimal solution of the subproblem, the optimal solution of the original problem can be obtained. No aftereffect; Once the state of a certain stage is determined, the evolution of the subsequent process is no longer affected by the previous states and decisions (the future has nothing to do with the past); When deducing the state of the later stage, only care about the specific state value of the previous stage, do not care about how the state is derived step by step

There was no aftereffect

How many ways can I go from 0, 0 to 4, 4? You can only go right and down

So let’s say dp of I, j is the way to go from 0, 0 to I, j

dp(i, 0) = dp(0, j) = 1

Dp (I, j) = dp(I, j – 1) + dp(I – 1, j)

There was no aftereffect

When deducing dp(I, j), only the values of dp(I, j-1) and dp(I — 1, j) are needed

We don’t need to worry about the values of dp(I, j-1) and dp(I – 1, j)

If you can walk left, right, up, and down, and you can’t walk the same cell twice

There are contingency of sex

What’s the next step for dp(I, j), and how did you get there

So how do you get dp(I, j-1) and dp(I – 1, j)?

change

We talked about this in the greedy algorithms video, but we only used greedy algorithms, and we didn’t get an optimal solution in this case

greedy

Today we use dynamic programming to solve this problem.

Question:

Suppose there are 25 cents, 20 cents, 5 cents, 1 cent coins, now want to give the customer 41 cents change, how to minimize the number of coins?

Let’s say dp of n is the minimum number of coins we need to get to n points

If you chose the 25 cent coin the first time, then dp(n) = dp(n – 25) + 1

If you chose the 20 cent coin the first time, then dp(n) = dp(n-20) + 1

If you chose the five-cent coin the first time, then dp(n) = dp(n-5) + 1

If I picked the 1 cent coin the first time, then DP (n) = DP (n-1) + 1

So the dp (n) = min {dp (n – 25), dp (n – 20), dp (n – 5), dp (n – 1)} + 1

Violence recursive

Example:

   static int coins1(int n) {
        if (n < 1) return Integer.MAX_VALUE;
        if (n == 25 || n == 20 || n == 5 || n == 1) return 1;
        int min1 = Math.min(coins1(n - 25), coins1(n - 20));
        int min2 = Math.min(coins1(n - 5), coins1(n - 1));
        return Math.min(min1, min2) + 1;
    }
Copy the code

Top-down calls, with overlapping subproblems

Mnemonic search

Example:

  static int coins2(int n) {
        if (n < 1) return -1;
        int[] dp = new int[n + 1];
        int[] faces = {1, 5, 20, 25};
        for (int face : faces) {
            if (n < face) break;
            dp[face] = 1;
        }
        return coins2(n, dp);
    }
    
    static int coins2(int n, int[] dp) {
        if (n < 1) return Integer.MAX_VALUE;
        if (dp[n] == 0) {
            int min1 = Math.min(coins2(n - 25, dp), coins2(n - 20, dp));
            int min2 = Math.min(coins2(n - 5, dp), coins2(n - 1, dp));
            dp[n] = Math.min(min1, min2) + 1;
        }
        return dp[n];
    }
Copy the code

Top down calls

Why do we use arrays to store values? Does someone want to use hashes to store values? So the problem comes, if we go to the bottom of the hash table, look at the implementation of the hash, we will find that the bottom implementation of the hash is to use arrays to complete, but in order to have a faster search speed, in the hash table, we open up a lot of array space may not be used. So we use arrays to reduce memory waste even more.

Recursive implementation

This method does not use recursion

Example:

static int coins3(int n) { if (n < 1) return -1; int[] dp = new int[n + 1]; for (int i = 1; i <= n; i++) { int min = Integer.MAX_VALUE; if (i >= 1) {min = Math.min(dp[i-1],min); } if (i >= 5) {min = Math.min(dp[i - 5], min); } if (i >= 20) {min = Math.min(dp[i - 20], min); } if (i >= 25) {min = Math.min(dp[i - 25], min); } dp[i] = min + 1; } return dp[n]; }Copy the code

If n is 41, we start at 1. According to the code, we use coins of value 1 until four, and then we use coins of value 5 after five…

The entire DP array stores the number of coins needed for each previous value, and each search is based on the minimum number of coins before, plus the one we want now,

The coins are divided into irregular groups based on the values assigned to them.

General implementation

Now we have solved the problem of change, but what we do is the fixed value of change, so it is impossible for the interviewer to give you the same question in the interview, even if the number in the code can be changed, what if the number given to you is different every time? So what? Can’t we change it every time? That’s impossible, so we need a general solution, but not to get you coded, but to get you to understand this type of problem in a deeper way.

So the first thing is based on this code up here, how do we know which coins we’re collecting each time

static int coins4(int n) { if (n < 1) return -1; int[] dp = new int[n + 1]; // Faces [I] faces = new int[dp.length]; // Faces [I] is the face of the last coin when I reach I. for (int i = 1; i <= n; i++) { int min = dp[i - 1]; faces[i] = 1; if (i >= 5 && dp[i - 5] < min) { min = dp[i - 5]; faces[i] = 5; } if (i >= 20 && dp[i - 20] < min) { min = dp[i - 20]; faces[i] = 20; } if (i >= 25 && dp[i - 25] < min) { min = dp[i - 25]; faces[i] = 25; } dp[i] = min + 1; print(faces, i); } // print(faces, n); return dp[n]; } static void print(int[] faces, int n) { System.out.print("[" + n + "] = "); while (n > 0) { System.out.print(faces[n] + " "); n -= faces[n]; } System.out.println(); }Copy the code

We use a Faces array to record the value of the last added coin, and as we work our way up, we know which coins it is made of.

    static int coins0(int n, int[] faces) {
        if (n < 1 || faces == null || faces.length == 0) return -1;
        int[] dp = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            int min = Integer.MAX_VALUE;
            for (int face : faces) {
                if (i < face) continue;
                min=Math.min(dp[i-face],min );
            }
            dp[i]=min+1;
        }
        return dp[n];
    }
Copy the code

We use an array to store the face value of the coin, and we use the for loop to do our previous judgment

Maximum continuous subsequence sum

Question:

Given a sequence of integers of length N, find its maximum continuous subsequence and the sum of such as — 2, 1, — 3, 4, — 1, 2, 1, — 5, 4 is 4 + (– 1) + 2 + 1 = 6

State definition

Assume that dp(I) is the maximum continuous subsequence ending in nums[I] and (nums is the entire sequence)

The largest continuous subsequence ending with nums[0] -2 is -2, so dp(0) = -2

The largest continuous subsequence ending in nums[1] 1 is 1, so dp(1) = 1

The largest continuous subsequence ending with NUMs [2] -3 is 1, -3, so dp(2) = dp(1) + (-3) = -2

The largest continuous subsequence ending in nums[3] 4 is 4, so dp(3) = 4

The largest continuous subsequence ending with NUMs [4] — 1 is 4 and — 1, so dp(4) = dp(3) + (– 1) = 3

The largest continuous subsequence ending with NUMs [5] 2 is 4, — 1, and 2, so dp(5) = dp(4) + 2 = 5

The largest continuous subsequence ending with NUMs [6] 1 is 4, — 1, 2, 1, so dp(6) = dp(5) + 1 = 6

The largest continuous subsequence ending with NUMs [7] — 5 is 4, — 1, 2, 1, — 5, so dp(7) = dp(6) + (– 5) = 1

The largest continuous subsequence ending with NUMs [8] 4 is 4, — 1, 2, 1, — 5, 4, so dp(8) = dp(7) + 4 = 5

State transition equations and initial states

The essence of dynamic programming; I think it’s the transition equation and the initial state, so we understand DP, we know what DP is, but if we have this problem, we can’t figure out his transition equation; We’re still at our wit’s end with this problem.

State transition equation

If dp(I — 1) ≤ 0 then dp(I) = nums[I]

If dp(I — 1) > 0, then dp(I) = dp(I — 1) + nums[I]

The initial state

The value of dp(0) is nums[0]

The final solution

Max {dp(I)}, I ∈ [0, nums.length)

In my opinion, the equation of state transition, at first, does not require you to write down the formula directly, but to understand how it changes, after slowly refining, finally summed up the formula, right

* Example: *

static int maxSubArray1(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        int max = dp[0];
        for (int i = 1; i < dp.length; i++) {
            int prev = dp[i - 1];
            if (prev <= 0) {
                dp[i] = nums[i];
            } else {
                dp[i] = prev + nums[i];
            }
            max = Math.max(dp[i], max);
        }
        return max;
    }
Copy the code

We create a DP array to store the maximum contiguous subsequence ending in each number

Space complexity O(n)

Time complexity O(n)

To optimize the

Why do we store those smaller values? We’re going to keep iterating, looking for the maximum, and sum is negative, and we’re going to be reducing ourselves, so we’re going to start at a new place

static int maxSubArray2(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        int dp = nums[0];
        int max = dp;
        for (int i = 1; i < nums.length; i++) {
            if (dp <= 0) {
                dp = nums[i];
            } else {
                dp = dp + nums[i];
            }
            max = Math.max(dp, max);
        }
        return max;
    }
Copy the code

Longest Ascending Subsequence (LIS)

Question:

Given an unordered sequence of integers, find the length of its longest ascending subsequence (strictly ascending)

For example, the longest ascending subsequence of [10, 2, 2, 5, 1, 7, 101, 18] is [2, 5, 7, 101] and [2, 5, 7, 18], with a length of 4

State definition

Suppose the array is NUMS, [10, 2, 2, 5, 1, 7, 101, 18]

Dp (I) is the length of the longest ascending subsequence ending with nums[I], I ∈ [0, nums.length)

The longest ascending subsequence ending in nums[0] 10 is 10, so dp(0) = 1

The longest ascending subsequence ending in nums[1] 2 is 2, so dp(1) = 1

The longest ascending subsequence ending in nums[2] 2 is 2, so dp(2) = 1

The longest ascending subsequence ending with NUMs [3] 5 is 2 and 5, so dp(3) = DP (1) + 1 = dp(2) + 1 = 2

The longest ascending subsequence ending in nums[4] 1 is 1, so dp(4) = 1

The longest ascending subsequence ending with NUMs [5] 7 is 2, 5, and 7, so dp(5) = dp(3) + 1 = 3

The longest ascending subsequence ending with NUMs [6] 101 is 2, 5, 7, 101, so dp(6) = dp(5) + 1 = 4

The longest ascending subsequence ending with NUMs [7] 18 is 2, 5, 7, and 18, so dp(7) = DP (5) + 1 = 4

The length of the longest ascending subsequence is the maximum of all dp(I) Max {dp(I)}, I ∈ [0, nums.length)

static int lengthOfLIS1(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        int[] dp = new int[nums.length];
        int max = dp[0] = 1;
        for (int i = 1; i < dp.length; i++) {
            dp[i] = 1;
            for (int j = 0; j < i; j++) {
                if (nums[i] <= nums[j]) continue;
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
            max = Math.max(dp[i], max);
        }
        return max;
    }
Copy the code

Binary search – implementation

Longest Common Subsequence (LCS)

The problem

Find the longest common subsequence length of two sequences

The longest common subsequence of [1, 3, 5, 9, 10] and [1, 4, 9, 10] is [1, 9, 10], with length 3

The longest common subsequence length of ABCBDAB and BDCABA is 4, possibly

ABCBDAB and BDCABA > BDAB

ABCBDAB and BDCABA > BDAB

ABCBDAB and BDCABA > BCAB

ABCBDAB and BDCABA > BCBA

The idea is the same as what we just did, where we had one value, now we have multiple values

The above solution is very similar to the previous one, and you should all understand it, but the following is the key point

As you can see from the figure, once we know each of these numerical patterns, we optimize our code again

This time we opened up a two-dimensional array, to maintain our number in the table, as a kind of more waste of space, but in fact, we can use the one dimensional array to maintain a line in a table, and then to the next line, we update for one dimensional array, by this time there will be a miracle happened, I will appear in the us to update the process of two lines up and down

And at this point, we can evaluate the value of the corner, and we’re defining a variable lefttop to record the value of the upper left corner, which is used to evaluate equality by 1

static int lcs(int[] num1,int[] num2){ if(num1==null||num1.length==0)return 0; if(num2==null||num2.length==0)return 0; int[] rowsnum=num1,closnum=num2; if(num2.length>num1.length){ rowsnum=num2; closnum=num1; } int[] dp=new int[closnum.length+1]; for(int i=1; i<=rowsnum.length; i++){ int cur=0; for (int j=1; j<=closnum.length; j++){ int lefttop=cur; cur=dp[j]; if(rowsnum[i-1]==closnum[j-1]){ dp[j]=lefttop+1; }else { dp[j]=Math.max(dp[j],dp[j-1]); } } } return dp[closnum.length]; }Copy the code

We’re just using an array of integers right now, so we should do it as a string, just like in Java, strings can look like arrays using the toCharArray() function