Recursive Algorithm and Recursive Routine (Part of Hand Tearing Algorithm)

As I said in the basics, recursion and dynamic programming have this ambiguous relationship, so to speak, dynamic programming is the recursion of a decision process. Therefore, our brush questions today will also involve some relatively simple dynamic programming topics, which will also help us to have a deep understanding of recursive algorithm, and lay a foundation for our further study of dynamic programming algorithms and optimization of dynamic programming.

First, pre-knowledge.

Usage scenario: When the state of the next (upper) row can be deduced only from the information of the upper (lower) row, and we are required to solve the last (first) row, we do not need to store the data of each row in the array, we can save space complexity by scrolling the array technique.

Concrete implementation: suppose we already know that the first line of data, and through the first line of the data after a certain operation can get the second row of the data, so we only need a temporary storage array two rows of data, after each line of data can be calculated, the result of the continuous rolling to replace the two rows of data, the final solution of the last line of the way of data.

Key point: Derive the index of the current row and the next (upper) row. Since the array is scrolled, the index of our target row changes over time. Here is a general formula for finding the current row and the upper (lower) row:

Const curIdx = I % 2; const curIdx = I % 2; Const preIdx = +! Since the scrolling array has only two rows and the index is either 0 or 1, we get the index of the top (bottom) row by inverting the front row (note that in JS, inverting 1 is false and inverting 0 is true, so we use an implicit cast to convert a Boolean to a numeric type).

Practical use: often used when brushing questions, see below

Two, brush topic dinner

2.1 LeetCode 120. Triangle minimum path sum

2.1.1 Solution ideas

According to the recursion routine we described earlier:

Define the recursive state: in this problem, the sum of the path of each step depends mainly on the current number of rows I and the current number of columns J, so our recursive state should be: dp[I, j]
Recursion formula: After determining the recursion state, we need to determine the recursion formula. So how do we derive the ith row and the j column? So first of all, by definition, we want the minimum path sum, so if we go up from the bottom, then we know that the next row of I is going to be the minimum legal path of the previous row of I +1 plus the current path to the node.

Therefore, we get the following formula:

/ / the ith row first j column data derived formula of dp [I, j) = min (dp/I + 1, j, dp/I + 1, j + 1) + val (I, j)Copy the code

Analyzing boundary conditions: we need to initialize the conditions we know about in our recursive array as boundary conditions. In this problem, the boundary condition is the data in the last row. We add the data in the last row to the scroll array first, so that we can deduce the total path sum continuously from the data in the last row to find the minimum path.
Program implementation: we directly use the loop and scroll array techniques.

2.1.2 Code demonstration

function minimumTotal(triangle: number[][]): number { const n = triangle.length; // dp[I,j] = min(dp[I +1, j], dp[I +1, j+1]) + val[I,j] Let dp: number[][] = []; for(let i=0; i<2; i++){ dp.push([]); } // First initialize the value of the last line, so the index of the last line should be (n-1)%2 for(let I =0; i<n; i++) { dp[(n-1)%2][i] = triangle[n-1][i]; } // Then evaluate for(let I = n-2; i>=0; Let idx = I %2; let idx = I %2; let nextIdx = +! idx; For (let j=0; j <= i; j++) { dp[idx][j] = Math.min(dp[nextIdx][j], dp[nextIdx][j + 1]) + triangle[i][j]; Return dp[0][0]; return dp[0]; };Copy the code

2.2 LeetCode 119. Yang Hui Triangle II

2.2.1 Solution ideas

This is similar to the last problem, but you can still derive the value of the next row from the previous row, so you still have to do the trick of scrolling through the array, and the analysis of the recursive state and the recursive formula is similar, so you can try to derive it yourself.

And the boundary condition for this problem is that every row has to start with a 1.

2.1.2 Code demonstration

function getRow(rowIndex: number): number[] { const res: number[][] = []; For (let I =0; i<2; i++)res.push(new Array(rowIndex+1).fill(0)); for(let i=0; i<=rowIndex; I ++) {let idx = I % 2; let preIdx = +! idx; res[idx][0] = 1; For (let j=1; j<=i; j++) { res[idx][j] = res[preIdx][j-1] + res[preIdx][j]; Return res[(rowIndex % 2)]};Copy the code

2.3 LeetCode 198

2.3.1 Solution idea

Recursive state analysis: Since the maximum amount that can be stolen is required, then assuming that the last house is N, then the maximum amount is directly related to whether we steal the last house, and we need to discuss by classification:

A. Do not steal the last house: DP [n][0] where 0 means do not steal b. Steal the last house: DP [n][1] Where 1 means steal

Determine the recursion formula: Since the recursion state is divided into two cases for discussion, our recursion formula should also be divided into two parts:

A. Don’t steal the last house: because we can’t steal two neighboring houses consecutively, if the last house doesn’t steal, then we can steal the penultimate house. Therefore, at this time, our maximum income depends on the amount of money stolen from the penultimate house and the maximum amount of money not stolen from the penultimate house. Dp [n][0] = Max (dp[n-1][0], dp[n-1][1]) b. Steal the last house: since the last house is stolen, the penultimate house cannot be stolen. Therefore, the maximum gain in this case is the gain from not stealing the penultimate house plus the gain from stealing the last house, i.e. Dp [n][1] = dp[n-1][0] + NUMs [n].

Determine boundary conditions:

If we didn’t steal the first house, because we didn’t steal any of the houses, the payoff would be 0. If you steal from the first house, the profit is the first house’s money. At this point, we have established our initial boundary conditions.

Program implementation: this problem because the current income only depends on the income of the last, so still use the rolling array skills and cycle implementation.

2.3.2 Code demonstration

function rob(nums: number[]): number { const n = nums.length; Dp [n][0] = Max (dp[n-1][0], dp[n-1][1]) Dp [n][1] = dp[n-1][0] + nums[n], i.e. : Const dp: number[][] = []; const dp: number[] = []; for(let i=0; i<2; i++) dp.push([]); Dp [0][0] = 0; Dp [0][1] = nums[0]; For (let I =1; i<n; I ++) {// use the scroll array trick let idx = I % 2; let preIdx = +! idx; dp[idx][0] = Math.max(dp[preIdx][0] , dp[preIdx][1]); dp[idx][1] = dp[preIdx][0] + nums[i]; Return math. Max (dp[(n-1) % 2][0], dp[(n-1) % 2][1]); };Copy the code

2.4 LeetCode 152. Product maximum subarray

2.4.1 Solution Idea

Recursive state analysis: We want the product of the largest subarray, so we can use dp[n] to represent the maximum value of the product of the largest subarray whose last bit is n.
There are two possibilities: the first possibility is to multiply the largest product of n-1 by the current value of n, and the second possibility is that n opens itself without multiplying the previous value. Therefore, we should choose a maximum in both cases, so the recursive formula should be: dp[n] = max(dp[n-1] * val[n], val[n])
Boundary conditions: Since the array may contain negative numbers, the current value may be multiplied by the original maximum value to become a minimum value, or the current value may be multiplied by the original minimum value to become a maximum value. Therefore, we need to record not only the maximum value before the current number, but also the minimum value to facilitate the handling of negative numbers. And at the beginning, since we’re looking for a product relationship, we can initialize both our maximum and minimum values to 1.
Program implementation: since the largest product of the NTH term only depends on n-1, we can use the variable way to store the relationship, no need to open up additional recursive array space.

2.4.2 Code demonstration

function maxProduct(nums: number[]): Number {// Recursion state: dp[n] represents the product of the longest continuous subarray ending in n Dp [n] = Max (dp[n-1] * val[n], val[n]); Their independence as a result from the two solutions / / we should choose a larger value as a result / / since the current value only keep up with a value, we can use variables to replace the recursive arrays, and because there may be a negative number in the array, is likely to lead to the maximum current value multiplied before into minimum value, therefore, Let res = number.min_safe_INTEGER; let res = number.min_safe_integer; Let min = 1; let min = 1; let max = 1; For (let num of nums) {// Since num is less than 0, if we still multiply it by the original maximum, it will become the minimum instead, so when num is less than 0, we swap the maximum and the minimum, so that num times the original minimum, If (num < 0) [min, Max] = [Max, min]; Min = math. min(min * num, num); max = Math.max(max * num, num); // The final result is the maximum value between the previous result and Max. } return res; };Copy the code

2.5 LeetCode 322. Change for change

2.5.1 Solution Ideas

Recursive state: How many coins we use depends on the denomination of the amount to be collected, so our recursive state is: dp[n]
Recursion: If we want to collect n coins, then the minimum number of coins we can collect should be the number of n-coins plus the current coin number 1, and take the minimum number of coins each time. Therefore, our final recursive formula should be: DP [n] = min(dp[i-coin] + 1), that is, we need to take a minimum value of the money in denomination N among all the piecing schemes, and each piecing scheme should be the current denomination I minus the coin denomination currently used plus the current coin number 1.
Boundary condition: when denomination is 0, we need 0 coins.
Program implementation: When we piece together denominations, there are some special cases to consider, such as: If the current denomination is smaller than the coin denomination, we can’t use the current coin to make the target denomination. If we can’t make the i-coin denomination, we certainly can’t make the target denomination with the i-coin denomination, because i-coins are a prerequisite.

2.5.2 Code demonstration

Function coinChange(coins: number[], amount: number): number {// We need to calculate the number of coins for each denomination. number[] = new Array(amount+1); Dp.fill (-1); Dp [0] = 0; // loop each value for(let I =1; i<=amount; I ++) {for(let coin of coins) {// If (I < coin) continue; If (dp[i-coin] === -1) continue; if(dp[i-coin] === -1) continue; // If the current matching scheme is not used, or the result of using the current matching scheme is larger than the result of the previous matching scheme, it means that we have found a smaller patchwork scheme. Then we will together to piece together before the plan to replace the current solution if (dp [I] = = = 1 | | dp > dp [I - "] [I] + 1) dp [I] = dp [I - "] + 1; } } return dp[amount]; };Copy the code

2.6 LeetCode 300. Longest increasing subsequence

2.6.1 Solution ideas

Concept literacy: a. Increasing subsequences: You can “skip” through a complete sequence, and the next element must be no smaller than the last. By “jumping”, we mean that the element index does not need to be consecutive, as in the following example:

# Original sequence 1, 4, 2, 2, 3, 5, 0, 6 # increment subsequence 1, 2, 2, 3, 5, 6Copy the code

B. Strict longest increasing subsequence: strict increasing subsequence adds a qualification condition on the basis of increasing subsequence, that is, the next element cannot be equal to the previous element, but can only be greater than, as shown in the following example:

# Original sequence 1, 4, 2, 2, 3, 5, 0, 6 # strictly incrementing subsequence 1, 2, 3, 5, 6Copy the code

Recursive state: Since the length of our longest increasing subsequence is related to which element I currently have as the last element, our recursive state is: dp[n], representing the length of the longest increasing subsequence ending at position N
Recursive formula: We want to figure out the length of the longest increasing subsequence ending in the NTH element, To find him on a legitimate the longest increasing subsequence of the last element j, and we end with the first n elements on the length of the longest increasing subsequence is a length of the longest increasing subsequence plus one, we just need to will all meet the conditions of the maximum length of the longest increasing subsequence graph it is the end result, that is: dp[n] = max(dp[j] + 1) | j<n & val(j) < val(n)
Boundary conditions: when n is 1, the longest increasing subsequence length is 1
Implementation: Since our recursive state defines the length of the longest increasing subsequence ending in n, we default to the initial value of each item to 1, at least the current number.

2.6.2 Code demonstration

function lengthOfLIS(nums: number[]): number { const dp: number[] = []; let res: number = Number.MIN_SAFE_INTEGER; for(let i=0; i<nums.length; Dp [I] = 1; dp[I] = 1; dp[I] = 1; dp[I] = 1; dp[I] = 1; dp[I] = 1; Nums [j] < num[I] for(let j = 0; j < i; j++) { if(nums[j] < nums[i]) dp[i] = Math.max(dp[i], dp[j] + 1); } res = math.max (res, dp[I]); } return res;Copy the code

Three, endnotes

That’s the end of today’s brush problem.

In fact, it is not difficult to find from the above problems that there are certain routines to follow, whether it is recursive algorithm or dynamic programming. Although this routine is not easy to learn, at least we have a clear learning direction. We can learn by: Recursive state definition, recursive formula (state transition equation) derivation, boundary condition establishment, program implementation these four general routines will analyze and solve a seemingly complicated recursive or dynamic program one by one.

Of course, the above program implementation, in order to make it easier to understand, did not use too many techniques for optimization, is not necessarily optimal, if the future opportunity, will share with you the optimization techniques of dynamic programming. Welcome to communicate with us more ~

-END-