Leetcode: dynamic programming [basic problem solving]

PS. This article is for reference Random code recording Some notes made , Please stamp the link for the full version , Very good tutorial ！

If there are a lot of questions Overlapping subproblems , Using dynamic programming is the most effective . Therefore, every state in dynamic programming must be derived from the previous state , This is distinguished from greed , Greed has no state , Instead, choose the best locally .

for example ： Yes N Items and one can carry a maximum weight of W The backpack . The first i The weight of the item is weight[i], The value is value[i]. Each item can only be used once , Solve which items are loaded into the backpack, and the total value of the items is the largest .

In dynamic programming dp[j] By dp[j-weight[i]] Derived from , And then take max(dp[j], dp[j - weight[i]] + value[i]). Greed is to choose the largest or smallest item every time you take it , It has nothing to do with the previous state .

Problem solving steps of dynamic programming ：

1. determine dp Array （dp table） And the meaning of subscripts
2. Determine the recurrence formula
3. dp How to initialize an array
4. Determine the traversal order
5. Give an example to deduce dp Array

\quad
\quad
Here are some basic topics ~

509. Fibonacci number

Fibonacci number （ Usually use F(n) Express ） The sequence formed is called Fibonacci sequence . The sequence is composed of 0 and 1 Start , Each of the following numbers is the sum of the first two numbers . That is to say ：

• F(0) = 0,F(1) = 1
• F(n) = F(n - 1) + F(n - 2), among n > 1

Given n , Please calculate F(n) .

Method 1 ： Simple recursion

class Solution:
    def fib(self, n: int) -> int:
        if n < 2: return n
        return self.fib(n - 1) + self.fib(n - 2)

Method 2 ：DP

class Solution:
    def fib(self, n: int) -> int:
        if n < 2: return n
        dp = [0] * (n + 1)
        dp[0] = 0
        dp[1] = 1

        for i in range(2, n + 1):
            dp[i] = dp[i - 1] + dp[i - 2]

        return dp[n]

The problem is very simple , There's nothing to say , You can see DP Methods take less time .

70. climb stairs

Suppose you're climbing the stairs . need n You can reach the top of the building . Every time you climb 1 or 2 A stair . How many different ways can you climb to the top of the building ？

This problem is actually Fibonacci sequence ！！

There's a way to get to the first floor , There are two ways to climb to the second floor . Then take two more steps to the third floor , Take the second step to the third . Therefore, the state of the stairs to the third floor can be deduced from the state of the stairs to the second floor and the state of the stairs to the first floor , So you can think of dynamic programming .

determine dp The meaning of arrays and subscripts ：dp[i]： Climb to No i Floor stairs , Yes dp[i] Methods .

The recursive formula ： from dp[i] The definition of ,dp[i] It can be pushed out in two directions .

• First of all dp[i - 1], On i-1 Floor stairs , Yes dp[i - 1] Methods , Then one more step is dp[i]
• And that is dp[i - 2], On i-2 Floor stairs , Yes dp[i - 2] Methods , Then jump two more steps is dp[i].

therefore dp[i] = dp[i - 1] + dp[i - 2].

class Solution:
    def climbStairs(self, n: int) -> int:
        if n <= 2: return n
        dp = [0] * (n + 1)
        dp[1] = 1
        dp[2] = 2
        for i in range(3, n + 1):
            dp[i] = dp[i - 1] + dp[i - 2]
        return dp[n]

746. Use the minimum cost to climb the stairs

Give you an array of integers cost , among cost[i] It's from the stairs i The cost of climbing a step up . Once you pay this fee , You can choose to climb up one or two steps . You can choose from the subscript to 0 Or subscript 1 The steps began to climb the stairs . Please calculate and return the minimum cost to reach the top of the stairs .

Example 1 It costs only one 15 You can get to the top of the stairs , The last step can be understood as no cost , That's important .

dp[i] The definition of ：

• Arrive at i The minimum amount of physical strength required for a step is dp[i].

The recursive formula ：

• There are two ways to get dp[i], One is dp[i-1] One is dp[i-2]. It must be the one with the least cost , therefore dp[i] = min(dp[i - 1], dp[i - 2]) + cost[i].（ In the question, every time you climb a ladder, you have to spend the corresponding physical strength , So this is cost[i]）

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        dp = [0] * len(cost)
        dp[0] = cost[0]
        dp[1] = cost[1]
        
        for i in range(2, len(cost)):
            dp[i] = min(dp[i - 1], dp[i - 2]) + cost[i]

        return min(dp[len(cost) - 1], dp[len(cost) - 2])

62. Different paths

A robot is in a m x n The top left corner of the grid （ The starting point is marked as “Start” ）. The robot can only move down or right one step at a time . The robot tries to reach the bottom right corner of the grid （ In the figure below, it is marked as “Finish” ）. Ask how many different paths there are in total ？

dp[i][j] Definition ： From (0, 0) set out , To (i, j) Yes dp[i][j] Different paths .

The recursive formula ：dp[i][j] = dp[i - 1][j] + dp[i][j - 1], because dp[i][j] It's just these two directions .

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        dp = [[0 for _ in range(n)] for _ in range(m)]

        for i in range(m):
            dp[i][0] = 1
        for j in range(n):
            dp[0][j] = 1

        for i in range(1, m):
            for j in range(1, n):
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1]

        return dp[m - 1][n - 1]

• Time complexity ：O(m × n)
• Spatial complexity ：O(m × n)

in fact ,dp Array using a one-dimensional array can solve the problem , You can optimize the point space . How do you understand that ？ Look at the picture below ：

As you can see from the picture above , Look on the lines , Update each cycle dp Array is updated on the basis of the previous line , That is to say, the previous line is actually covered every time . So a one-dimensional array can solve the problem .

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        dp = [1 for _ in range(n)]

        for i in range(1, m):
            for j in range(1, n):
                dp[j] += dp[j - 1]
                
        return dp[n - 1]

• Time complexity ：O(m × n)
• Spatial complexity ：O(n)

Method 3 ： Number theory method

altogether $m$ That's ok ,$n$ Column words , You can see , From start to end , At least we need to go $m+n-2$ Step . Here $m+n-2$ In step , There must be $m-1$ The next step is to go down , It doesn't matter when you go down . Then there are several ways ？ Can be converted to , Yes $m+n-2$ A different number , whatever $m-1$ Number , There are several ways . Isn't this a combinatorial problem ？ That is to say, there are $C_{m+n-2}^{m-1}$ Methods , You know the calculation formula ？ Direct write ！

class Solution:
  def uniquePaths(self, m: int, n: int) -> int:
        numerator = 1  #  molecular 
        denominator = 1  #  The denominator 
        count = m - 1
        t = m + n - 2
        #  Calculate the molecules 
        while count:
            count -= 1
            numerator *= t
            t -= 1

        #  Calculate denominator 
        for i in range(1, m):
            denominator *= i

        return int(numerator / denominator)

Python Don't worry about overflow , So it's simpler , Just follow the formula directly .

63. Different paths II

A robot is in a m x n The top left corner of the grid （ The starting point is marked as “Start” ）. The robot can only move down or right one step at a time . The robot tries to reach the bottom right corner of the grid （ In the figure below, it is marked as “Finish”）. Now consider the obstacles in the grid . So how many different paths will there be from the top left corner to the bottom right corner ？ Obstacles and empty positions in the grid are used respectively 1 and 0 To express .

dp[i][j] The definition of ： From (0, 0) set out , To (i, j) Yes dp[i][j] Different paths .

The recursive formula ：dp[i][j] = dp[i - 1][j] + dp[i][j - 1].

Be careful ：(i, j) If it's an obstacle, you should keep the initial state （ The initial state is 0）.

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        m, n = len(obstacleGrid), len(obstacleGrid[0])
        dp = [[0 for _ in range(n)] for _ in range(m)]
        
        #  Initialize the first column 
        for i in range(m):
            if obstacleGrid[i][0] == 1: break
            dp[i][0] = 1
        
        #  Initialize the first line 
        for j in range(n):
            if obstacleGrid[0][j] == 1: break
            dp[0][j] = 1

        for i in range(1, m):
            for j in range(1, n):
                if obstacleGrid[i][j] == 0:
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1]

        return dp[m - 1][n - 1]

• Time complexity ：O(n × m),n、m Respectively obstacleGrid Length and width
• Spatial complexity ：O(n × m)

343. integer partition

Given a positive integer n , Divide it into k individual Positive integer And （ k >= 2 ）, And maximize the product of these integers . return The maximum product you can get .

dp[i]： Split numbers i, The maximum product that can be obtained is dp[i].

The recursive formula ： from 1 Traverse j, Then there are two ways to get dp[i]：

• One is j * (i - j) Direct multiplication .
• One is j * dp[i - j], It's equivalent to splitting (i - j)

j It's from 1 To traverse the , In a traverse j In the process of j The split of has been calculated . So from 1 Traverse j, Compare (i - j) * j and dp[i - j] * j Take one of the biggest . therefore , The recursive formula ：dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j)).

Be careful ： from dp[i] By definition ,dp[0] and dp[1] You shouldn't initialize , That is, meaningless values .

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

96. Different binary search trees （）

Give you an integer n , Seek just by n Composed of nodes with node values from 1 To n Different from each other Binary search tree How many kinds? ？ Returns the number of binary search trees satisfying the meaning of the question .

**dp[i]** Definition ：1 To **i** The number of binary search trees composed of nodes is **dp[i]**.

Recursive formula is a little complicated , Let's take a specific look at ：

about $n=1$ The situation of ：

Obviously , There is only one case .

about $n=2$ The situation of ：

It's also obvious , There are only two cases . We can split it into two cases according to the head node ：

• Elements 1 Is the head node ： The number of nodes in the left subtree is 0（1 In this case ）, The number of nodes in the right subtree is 1（1 In this case ）;
• Elements 2 Is the head node ： The number of nodes in the left subtree is 1（1 In this case ）, The number of nodes in the right subtree is 0（1 In this case ）;

Why do you think so ？ This is to deduce from the following situation .（ It's hard to think ！）

about $n=3$ The situation of ：

This is not very nice , We split it into three cases according to the head node ：

• Elements 1 Is the head node ： The number of nodes in the left subtree is 0（1 In this case ）, The number of nodes in the right subtree is 2（2 In this case ）;
• Elements 2 Is the head node ： The number of nodes in the left subtree is 1（1 In this case ）, The number of nodes in the right subtree is 1（1 In this case ）;
• Elements 3 Is the head node ： The number of nodes in the left subtree is 2（2 In this case ）, The number of nodes in the right subtree is 0（1 In this case ）;

in other words , We can draw the following conclusion ：

• Elements 1 The number of search trees for the head node = Right subtree has 2 Number of search trees of elements * Zuo Zi Shu you 0 Number of search trees of elements
• Elements 2 The number of search trees for the head node = Right subtree has 1 Number of search trees of elements * Zuo Zi Shu you 1 Number of search trees of elements
• Elements 3 The number of search trees for the head node = Right subtree has 0 Number of search trees of elements * Zuo Zi Shu you 2 Number of search trees of elements

Besides , We can know ：

• Yes 2 The number of search trees per element is dp[2].
• Yes 1 The number of search trees per element is dp[1].
• Yes 0 The number of search trees per element is dp[0].

Take a look back. dp Definition of array ,dp[3] Is the element 1 The number of search trees for the head node + Elements 2 The number of search trees for the head node + Elements 3 The number of search trees for the head node . namely ：
dp[3] = dp[2] * dp[0] + dp[1] * dp[1] + dp[0] * dp[2]

According to this idea , We can deduce the following recurrence formula ：dp[i] += dp[ With j Is the number of nodes in the left subtree of the head node ] * dp[ With j Is the number of nodes in the right subtree of the head node ].j Equivalent to the element of the head node , from 1 Traversing i until . So the recurrence formula ：dp[i] += dp[j - 1] * dp[i - j],j-1 by j Is the number of nodes in the left subtree of the head node ,i-j For j Is the number of nodes in the right subtree of the head node .

As can be seen from the recurrence formula , The basis of derivation is dp[0]. So just initialize dp[0] that will do . The empty node is also a binary search tree , So initialization dp[0]=1 No problem ！

In terms of recursive formulas ,dp[ With j Is the number of nodes in the left subtree of the head node ] * dp[ With j Is the number of nodes in the right subtree of the head node ] China and Israel j It is the head node and the number of left subtree nodes is 0, Also needed dp[ With j Is the number of nodes in the left subtree of the head node ] = 1, Otherwise, the result of multiplication will become 0 了 .

Code implementation ：

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]

• Time complexity ：$O(n^2)$
• Spatial complexity ：$O(n)$

\quad
\quad
\quad
\quad

Ongoing update …