This article is participating in the “Java Theme Month – Java brush questions clock”, see < activity links > for more details.

【Java brush questions punch card 】 Brushing questions is much better than playing games, and the sense of achievement is getting stronger and stronger. I insist on brushing several questions every day, exercising for 30 minutes every day, waiting for 8-block abs and waiting for offers from big factories.

Then do it! This column is all about dynamic planning, I will start from the shallow to the deep, step by step, brush questions is such a need for continuous memory – Ebbinghaus memory method 2121112. There isn’t much about dynamic programming, but it’s a must for every programmer


This is a classic 😄😄😄 \color{green}{😄 😄 😄 ~}

What problem can I choose to do dynamic programming?

Counting 1.

How many ways can I get to the bottom right corner

How many ways can I pick the sum of k numbers yes is sum

2. Find the maximum and minimum

The maximum numeric sum of the path from the upper left corner to the lower right corner

Maximum ascending subsequence length

3. Seek existence

Stone game, whether the first hand will win

Can we pick k numbers such that the sum is sum

Leecode 96. Different binary search trees

Given an integer n, find 1… How many kinds of binary search trees can n be nodes? Example:

Input: 3

Output: 5

Explanation:

Given n = 3, there are five binary search trees with different structures:

The first thing to know about binary search trees is that the root node is larger than the left node and the right node is smaller.

Four steps for dynamic planning ~~~ ❤️❤️❤️❤️

2.1. Dynamic planning component 1: State determination

To put it simply, when solving dynamic programming, you need to open an array. What does each element of the array f[I] or f[I][j] represent, similar to what x, y, and z represent in mathematical problems

The last step

Given an ordered sequence 1 through n, to construct a binary search tree, we can traverse each number II as the root, the sequence 1 through (i-1) as the left subtree, and the sequence (I +1) through N as the right subtree. Then we can recursively build left and right subtrees in the same way.

During the above construction, we were able to ensure that each binary search tree was unique because the values of the roots were different.

subproblems

Thus, the original problem can be decomposed into two smaller sub-problems, and the solutions of the sub-problems can be reused. So we can think of using dynamic programming to solve this problem.

2.2. Dynamic programming component 2: Transfer equation

Assuming that the number of binary sorting trees with n nodes is G (n), let f(I) be the number of binary search trees with I as the root, then

G(n) = f(1) + f(2) + f(3) + f(4) + … + f(n)

When I is the root node, the number of left subtree nodes is I-1 and the number of right subtree nodes is N-i, then F (I) = G(i-1)*G(n-i)

So why is this cartesian product? \color{red}{why is the cartesian product? Why is this cartesian product?

Simple second formula can get into the first formula (LAN) carter formula G (n) = G (0) G (n – 1) + G (1) (n – 2) +… +G(n-1)*G(0)

2.3. Dynamic programming component 3: Initial conditions and boundary cases

When the sequence length is 1 (only roots) or 0 (empty tree), there is only one case, namely G(0)=1,G(1)=1

2.4. Dynamic programming component 4: Order of calculation

The top-down

Reference code

JAVA version

    public int numTrees(int n) {
        int[] dp = new int[n+1];
        dp[0] = 1;
        dp[1] = 1;
        
        for(int i = 2; i < n + 1; i++)
            for(int j = 1; j < i + 1; j++) 
                dp[i] += dp[j-1] * dp[i-j];
        
        return dp[n];
    }

Copy the code

Thank you for reading this, if this article is well written and if you feel there is something to it

Ask for a thumbs up 👍 ask for attention ❤️ ask for share 👥 for 8 abs I really very useful!!

If there are any mistakes in this blog, please comment, thank you very much! ❤ ️ ❤ ️ ❤ ️ ❤ ️