LeetCode Day 41 (day 40 is rest day) Dynamic Programming (3/17)

Coming to the third day of Dynamic Programming, the questions will show a blend of previous content, for example, the second question will have a BST

Question 1

343. Integer Break

Given an integer n, break it into the sum of k positive integers, where k >= 2, and maximize the product of those integers.

Return the maximum product you can get.

At least split into two numbers, the highest no upper limit, then how to split it?

Still have to rely on dynamic programming to solve the problem, according to the analysis process of dynamic programming to think:

1. determine the dp array (dp table) and the meaning of the subscripts

dp[i]: split the number i, the maximum product that can be obtained for dp[i].

The definition of dp[i] will be implemented throughout the solution process, the following step which do not understand, think of dp[i] is what!

1. Determine the recursive formula

You can think about how to get the maximum product of dp[i].

In fact, you can traverse j from 1, and then there are two channels to get dp[i].

One is j * (i - j) direct multiplication.

One is j * dp[i - j], which is equivalent to splitting (i - j). If you don’t understand this splitting, you can recall the definition of the dp array.

So the recursion formula: dp[i] = max({dp[i], (i - j) * j, dp[i - j] * j});

1. Initialisation of dp

Here only dp[2] = 1 is initialised, there is no disagreement from the definition of dp[i] that splitting the number 2 gives a maximum product of 1!

1. Determine the order of traversal

Let’s start with the recursive formula: dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j));

dp[i] is dependent on the state of dp[i - j], so traversing i must be a front-to-back traversal, with dp[i - j] before dp[i].

1. Derivation of the dp array as an example

An example of the values in the dp array when n is 10 is as follows:

2 3 4 5 6 7 8 9 10

1 2 4 6 9 12 18 27 36

So the code is as follows:

class Solution:
    def integerBreak(self, n: int) -> int:
        dp = [0] * (n + 1)   
        dp[2] = 1  
 
        for i in range(3, n + 1):
          
            for j in range(1, i // 2 + 1): 
                
                dp[i] = max(dp[i], (i - j) * j, dp[i - j] * j)
        
        return dp[n] 

Question 2

96. Unique Binary Search Trees

Given an integer n, return the number of structurally unique BST’s (binary search trees) which has exactly n nodes of unique values from 1 to n.

When n is 3, this can be deduced from the state where n is equal to 1 and 2.

dp[3], that is Number of search trees where element 1 is the head node search tree + Number of search trees where element 2 is the head node search tree + Number of search trees where element 3 is the head node search tree

Number of search trees with element 1 as the head node search tree = Number of search trees with 2 elements in the right subtree * Number of search trees with 0 elements in the left subtree

Element 2 is the number of head node search trees = the number of search trees with 1 element in the right subtree * the number of search trees with 1 element in the left subtree

Number of search trees with element 3 as head node = number of search trees with 0 elements in the right subtree * number of search trees with 2 elements in the left subtree

class Solution:
    def numTrees(self, n: int) -> int:
        dp = [0] * (n + 1)  
        dp[0] = 1  
        for i in range(1, n + 1):  
            for j in range(1, i + 1):  
                dp[i] += dp[j - 1] * dp[i - j]  
        return dp[n]