2312. Selling wood blocks | things about the interviewer and crazy Zhang San (leetcode, with mind map + all solutions)

zero title ： Algorithm （leetcode, With mind map + All solutions ）300 Title （2312） Selling wood blocks

One Title Description

Two Solution overview （ Mind mapping ）

3、 ... and All solutions

interviewer ： You're almost ready , Let's start the interview .

Madman Zhang San ：okk~

interviewer ： If the title is almost read , Say what you think 、 Thinking ha ~

Madman Zhang San ： Because in the title , contain “ most ” The word , So I think we should give priority to using “ Dynamic programming ” .

interviewer ： What do you think are the conditions for using dynamic programming ？

Madman Zhang San ： I personally think , You should have 2 Conditions ：

1） Optimal substructure

2） No aftereffect

interviewer ： very good , Do you know the essence of dynamic programming and the steps of problem solving ？

Madman Zhang San ：

1） The essence ： A technology that trades space for time

2） The problem solving steps ： branch 3 Step . State definition ： Decisions for each state , Store variables for each state ; State transition equation ： The transition relationship between the current state and the previous state ; The initial state ： Initial state or boundary conditions .

interviewer ： Young man , All right . I think you've almost warmed up , Then use the above knowledge to solve this problem ~

Aside ： After that 5-10 minute , Zhang San is slow to write the code .

interviewer ：（ A dignified face 、 confused ） Do you only recite relevant concepts , Haven't you coded relevant topics ？

Madman Zhang San ：（ Zhang Sanmian leaks timid color ） forehead ....

interviewer ： such , You think of the wood block as a big watermelon , Writing code will also be cool and refreshing ~
Then the topic becomes —— Do you have 1 Two dimensional （ The length is w、 Width is h） Big watermelon , You can choose to sell it directly （ If someone has to buy it at this time, the length is w、 Width is h）, Otherwise, the big watermelon at this time can only be obtained 0 element

Madman Zhang San ： Right , Then we can choose not to sell big watermelons at this time , Horizontal 、 Cut melons vertically , Cut the big watermelon into different small ones constantly , Finally, from these melon cutting schemes, the maximum selling price of the current large watermelon is calculated .

interviewer ： Yes , According to what you said before , write down State definition and State transition equation ~

Madman Zhang San ： well .

I understand the definition of state —— dp[i][j], The length is i、 Width is j when , The maximum amount of money you can get .

State transition equation —— When cutting melons horizontally ：dp[i][j] = max(dp[i][j], dp[k][j] + dp[i - k][j]),k For the range of [1, i - 1].
When cutting melons vertically ：dp[i][j] = max(dp[i][j], dp[i][k] + dp[i][j - k]),k For the range of [1, j - 1].

interviewer ： What about the initialization of the state ？

Madman Zhang San ： According to the array prices , To initialize —— When i、j Exist in prices Inside 0、1 When subscript position ,dp[i][j] = prices[ The corresponding element subscript ][2].

interviewer ： very good , Now that the idea has been clarified , Then start your performance , Ah No 、 Start writing your code ~

side ： Zhang San was instantly opened up like Ren Du's two veins , Three, five, two , Less than 10 The code was knocked out in minutes ~

1 programme 1

1) Code ：

//  programme 1 “ Dynamic programming  -  Normal version ”.
// “ skill ： The question stem contains   most   The word , Give priority to dynamic programming （ The essence ： Space for time technology ）.”
//  Reference resources ：
// 1）https://leetcode.cn/problems/selling-pieces-of-wood/solution/mai-mu-tou-kuai-by-leetcode-solution-gflg/
// 2）https://leetcode.cn/problems/selling-pieces-of-wood/solution/by-endlesscheng-mrmd/

//  idea （ Think of the wood block here as a big watermelon , Writing code will also be cool and refreshing ~）：
// 1） State definition ：dp[i][j], The length is i、 Width is j when , The maximum amount of money you can get .
// 2） State shift ：
// 2.1） Transverse cut ：dp[i][j] = max(dp[i][j], dp[k][j] + dp[i - k][j]),k For the range of  [1, i - 1].
// 2.2） Longitudinal cutting ：dp[i][j] = max(dp[i][j], dp[i][k] + dp[i][j - k]),k For the range of  [1, j - 1].

//  Ideas ：
// 1.1） State initialization ：l = prices.length; 
// dp = new Array(m + 1).fill(1).map(v => new Array(n + 1).fill(0));
//  reflection ： Why do every element of two dimensions go first   Default fill 0 ？
// 1.2） State initialization ： Traverse   Array  prices , Further initialization   Array  dp .

// 2） The core ： State shift .
// 2.1） Transverse cut ：dp[i][j] = max(dp[i][j], dp[k][j] + dp[i - k][j]),k For the range of  [1, i - 1].
// 2.2） Longitudinal cutting ：dp[i][j] = max(dp[i][j], dp[i][k] + dp[i][j - k]),k For the range of  [1, j - 1].

// 3） Return results  dp[m][n] .
var sellingWood = function(m, n, prices) {
    
    // 1.1） State initialization ：l = prices.length; 
    // dp = new Array(m + 1).fill(1).map(v => new Array(n + 1).fill(0));
    //  reflection ： Why do every element of two dimensions go first   Default fill 0 ？
    const l = prices.length;
    let dp = new Array(m + 1).fill(1).map(v => new Array(n + 1).fill(0));

    // 1.2） State initialization ： Traverse   Array  prices , Further initialization   Array  dp .
    for (let i = 0; i < l; i++) {
    
        const [width, height, price] = prices[i];
        dp[width][height] = price;
    }
    
    // 2） The core ： State shift .
    for (let i = 1; i <= m; i++) {
    
        for (let j = 1; j <= n; j++) {
    
            // 2.1） Transverse cut ：dp[i][j] = max(dp[i][j], dp[k][j] + dp[i - k][j]),k For the range of  [1, i - 1].
            for (let k = 1; k < i; k++) {
    
                dp[i][j] = Math.max(dp[i][j], dp[k][j] + dp[i - k][j]);
            }
            // 2.2） Longitudinal cutting ：dp[i][j] = max(dp[i][j], dp[i][k] + dp[i][j - k]),k For the range of  [1, j - 1].
            for (let k = 1; k < j; k++) {
    
                dp[i][j] = Math.max(dp[i][j], dp[i][k] + dp[i][j - k]);
            }
        }
    }

    // 3） Return results  dp[m][n] .
    return dp[m][n];
};

2 programme 2

interviewer ：Good. The code structure is very hierarchical , Notes are also placed in a very appropriate position ~

Madman Zhang San ： After all, this “ Two dimensional big watermelon ” It's cooked , I'm sure the algorithm here must be optimal , It can guarantee the highest selling price of our big watermelons .

interviewer ： Are you sure you “ Big watermelon cutting algorithm ” Is it cooked ？ I don't think so ？

Madman Zhang San ： I am a 1 A serious legal person , I can also write for you “ Raw melon algorithm ” no ？

interviewer ： I ask you , this “ Big watermelon cutting algorithm ” Is it cooked ？

Madman Zhang San ： Just say whether I can pass this interview ~

interviewer ：

Madman Zhang San ： Then I'm looking at 、 Think about optimizing

Aside ： I saw Zhang San write the code running process on the paper .
…
dp[5][5] = max(dp[5][5], dp[1][5] + dp[4][5], dp[2][5] + dp[3][5], dp[3][5] + dp[2][5], dp[2][5] + dp[1][5])
…

Madman Zhang San ： It seems that there are some optimization points —— There are a lot of redundant calculations , We subscript k Just enumerate to half the position —— namely k For the range of [1, i / 2（ Rounding down ）] .

1) Code ：

//  programme 2 “ Dynamic programming  -  Optimized version ”.
// “ skill ： The question stem contains   most   The word , Give priority to dynamic programming （ The essence ： Space for time technology ）.”
//  Reference resources ：
// 1）https://leetcode.cn/problems/selling-pieces-of-wood/solution/mai-mu-tou-kuai-by-leetcode-solution-gflg/
// 2）https://leetcode.cn/problems/selling-pieces-of-wood/solution/by-endlesscheng-mrmd/

//  idea （ Think of the wood block here as a big watermelon , Writing code will also be cool and refreshing ~）：
// 1） State definition ：dp[i][j], The length is i、 Width is j when , The maximum amount of money you can get .
// 2） State shift ：
// 2.1） Transverse cut ：dp[i][j] = max(dp[i][j], dp[k][j] + dp[i - k][j]),k For the range of  [1, i - 1].
// 2.2） Longitudinal cutting ：dp[i][j] = max(dp[i][j], dp[i][k] + dp[i][j - k]),k For the range of  [1, j - 1].

//  Ideas ：
// 1.1） State initialization ：l = prices.length; 
// dp = new Array(m + 1).fill(1).map(v => new Array(n + 1).fill(0));
//  reflection ： Why do every element of two dimensions go first   Default fill 0 ？
// 1.2） State initialization ： Traverse   Array  prices , Further initialization   Array  dp .

// 2） The core ： State shift （ There is optimization , There is symmetry ,k Enumerate to i、j Of 1 Half position is enough ）.
// 2.1） Transverse cut ：dp[i][j] = max(dp[i][j], dp[k][j] + dp[i - k][j]),k For the range of  [1, i / 2（ Rounding down ）].
// 2.2） Longitudinal cutting ：dp[i][j] = max(dp[i][j], dp[i][k] + dp[i][j - k]),k For the range of  [1, j / 2（ Rounding down ）].

// 3） Return results  dp[m][n] .
var sellingWood = function(m, n, prices) {
    
    // 1.1） State initialization ：l = prices.length; 
    // dp = new Array(m + 1).fill(1).map(v => new Array(n + 1).fill(0));
    //  reflection ： Why do every element of two dimensions go first   Default fill 0 ？
    const l = prices.length;
    let dp = new Array(m + 1).fill(1).map(v => new Array(n + 1).fill(0));

    // 1.2） State initialization ： Traverse   Array  prices , Further initialization   Array  dp .
    for (let i = 0; i < l; i++) {
    
        const [width, height, price] = prices[i];
        dp[width][height] = price;
    }
    
    // 2） The core ： State shift .
    for (let i = 1; i <= m; i++) {
    
        for (let j = 1; j <= n; j++) {
    
            // 2.1） Transverse cut ：dp[i][j] = max(dp[i][j], dp[k][j] + dp[i - k][j]),k For the range of  [1, i / 2（ Rounding down ）].
            for (let k = 1; k <= Math.floor(i / 2); k++) {
    
                dp[i][j] = Math.max(dp[i][j], dp[k][j] + dp[i - k][j]);
            }
            // 2.2） Longitudinal cutting ：dp[i][j] = max(dp[i][j], dp[i][k] + dp[i][j - k]),k For the range of  [1, j / 2（ Rounding down ）].
            for (let k = 1; k <= Math.floor(j / 2); k++) {
    
                dp[i][j] = Math.max(dp[i][j], dp[i][k] + dp[i][j - k]);
            }
        }
    }

    // 3） Return results  dp[m][n] .
    return dp[m][n];
};

Aside ： Zhang San finished the above code , Hurriedly ask the interviewer .

Madman Zhang San ： Passed the interview ？

interviewer ：

Madman Zhang San ：

also 1 individual offer, Then I will take the post immediately CEO 了 , I should go to eat in the evening Shaxian snacks Well ？ still Lanzhou hand-pulled noodles Well ？ Ah , Too many choices are also a worry ！

Four Resource sharing & more

1 Article history - The overview

Article title	solution	Reading volume
1. Sum of two numbers （Two Sum）	common 3 Kind of	2.7 k+
2. Addition of two numbers （Add Two Numbers）	common 4 Kind of	2.7 k+
3. Longest substring without repeating characters （Longest Substring Without Repeating Characters）	common 3 Kind of	2.6 k+
4. Find the median of two positive arrays （Median of Two Sorted Arrays）	common 3 Kind of	2.8 k+
5. Longest text substring （Longest Palindromic Substring）	common 4 Kind of	2.8 k+
6. Z Font conversion （ZigZag Conversion）	common 2 Kind of	1.9 k+
7. Integer inversion （Reverse Integer）	common 2 Kind of	2.4 k+
8. String conversion integers (atoi)（String to Integer (atoi)）	common 3 Kind of	4.2 k+
9. Palindrome number （Palindrome Number）	common 3 Kind of	4.3 k+
11. Container for the most water （Container With Most Water）	common 5 Kind of	4.0 k+
12. Integer to Roman number （Integer to Roman）	common 3 Kind of	3.2 k+
13. Roman numeral to integer （Roman to Integer）	common 3 Kind of	3.8 k+
14. The longest common prefix （Longest Common Prefix）	common 4 Kind of	3.0 k+
15. Sum of three numbers （3Sum）	common 3 Kind of	60.7 k+
16. The closest sum of three （3Sum Closest）	common 3 Kind of	4.7 k+
17. Letter combination of telephone number （Letter Combinations of a Phone Number）	common 3 Kind of	3.1 k+
18. Sum of four numbers （4Sum）	common 4 Kind of	11.5 k+
19. Delete the last of the linked list N Nodes （Remove Nth Node From End of List）	common 4 Kind of	1.2 k+
20. Valid parenthesis （Valid Parentheses）	common 2 Kind of	1.8 k+
21. Merge two ordered lists （Merge Two Sorted Lists）	common 3 Kind of	1.2 k+
22. Bracket generation （Generate Parentheses）	common 4 Kind of	1.1 k+
23. Merge K An ascending list （Merge k Sorted Lists）	common 4 Kind of	0.9 k+
24. Two or two exchange nodes in a linked list （Swap Nodes in Pairs）	common 3 Kind of	0.5 k+
25. K A set of flip list （Reverse Nodes in k-Group）	common 5 Kind of	1.3 k+
26. Remove duplicate items from an ordered array （Remove Duplicates from Sorted Array）	common 4 Kind of	1.3 k+
27. Remove elements （Remove Element）	common 4 Kind of	0.4 k+
28. Realization strStr()（Implement strStr()）	common 5 Kind of	0.8 k+
29. Divide two numbers （Divide Two Integers）	common 4 Kind of	0.6 k+
30. Concatenate the substrings of all words （Substring with Concatenation of All Words）	common 3 Kind of	0.6 k+
31. Next spread （Next Permutation）	common 2 Kind of	0.8 k+
32. Longest valid bracket （Longest Valid Parentheses）	common 2 Kind of	1.4 k+
33. Search rotation sort array （Search in Rotated Sorted Array）	common 3 Kind of	1.0k+
34. Find the first and last positions of the elements in the sort array （Find First and Last Position of Element in Sorted Array）	common 3 Kind of	0.5 k+
35. Search insert location （Search Insert Position）	common 3 Kind of	0.3 k+
36. Effective Sudoku （Valid Sudoku）	common 1 Kind of	0.6 k+
38. Look-and-say sequence （Count and Say）	common 5 Kind of	1.1 k+
39. Combinatorial summation （Combination Sum）	common 3 Kind of	1.4 k+
40. Combinatorial summation II（Combination Sum II）	common 2 Kind of	1.6 k+
41. First positive number missing （First Missing Positive）	common 3 Kind of	1.2 k+
53. Maximum subarray and （Maximum Subarray）	common 3 Kind of	0.3k+
88. Merge two ordered arrays （Merge Sorted Array）	common 3 Kind of	0.4 k+
102. Sequence traversal of binary tree （Binary Tree Level Order Traversal）	common 3 Kind of	0.4 k+
146. LRU cache （LRU Cache）	common 2 Kind of	0.5 k+
160. Intersecting list （Intersection of Two Linked Lists）	common 2 Kind of	0.1 k+
200. Number of Islands （Number of Islands）	common 4 Kind of	0.1 k+
206. Reverse a linked list （Reverse Linked List）	common 3 Kind of	1.0 k+
215. The... In the array K The biggest element （Kth Largest Element in an Array）	common 3 Kind of	0.5 k+
236. The nearest common ancestor of a binary tree （Lowest Common Ancestor of a Binary Tree）	common 3 Kind of	0.1 k+
2119. Number reversed twice （A Number After a Double Reversal）	common 2 Kind of	0.3 k+
2120. Execute all suffix instructions （Execution of All Suffix Instructions Staying in a Grid）	common 1 Kind of	0.4 k+
2124. Check all A All in B Before （Check if All A’s Appears Before All B’s）	common 4 Kind of	0.4 k+
2125. The number of laser beams in the bank （Number of Laser Beams in a Bank）	common 3 Kind of	0.3 k+
2126. Destroy asteroids （Destroying Asteroids）	common 2 Kind of	1.6 k+
2129. Capitalize title （Capitalize the Title）	common 2 Kind of	0.6 k+
2130. The largest twins in the linked list are （Maximum Twin Sum of a Linked List）	common 2 Kind of	0.6 k+
2133. Check whether each row and column contains all integers （Check if Every Row and Column Contains All Numbers）	common 1 Kind of	0.6 k+

2 About bloggers

Ma Nong San Shao , One dedicated to writing The minimalist 、 But complete solutions （ Algorithm ） Bloggers .
Focus on Solve more than one problem 、 Structured thinking , Welcome to brush it together LeetCode ~