当前位置：网站首页>dynamic programming

dynamic programming

2022-06-27 12:58:00 【51CTO】

1. Fibonacci sequence

 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) .

 Example  1：

 Input ：n = 2
 Output ：1
 explain ：F(2) = F(1) + F(0) = 1 + 0 = 1
 Example  2：

 Input ：n = 3
 Output ：2
 explain ：F(3) = F(2) + F(1) = 1 + 1 = 2
 Example  3：

 Input ：n = 4
 Output ：3
 explain ：F(4) = F(3) + F(2) = 2 + 1 = 3
 
 Tips ：

0 <= n <= 30

     
      1.
      2.
      3.
      4.
      5.
      6.
      7.
      8.
      9.
      10.
      11.
      12.
      13.
      14.
      15.
      16.
      17.
      18.
      19.
      20.
      21.
      22.
      23.
      24.
      25.

Answer key ：

class Solution:
    def fib(self, n: int) -> int:
        if n == 0:
            return 0

        if n == 1:
            return 1

        dp = [0] * (n + 1)  #  Definition  dp  Array 
        dp[0] = 0   #  initialization 
        dp[1] = 1

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

        return dp[n]

     1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.

2. climb stairs

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 ？

 Example  1：

 Input ：n = 2
 Output ：2
 explain ： There are two ways to climb to the top .
1. 1  rank  + 1  rank 
2. 2  rank 
 Example  2：

 Input ：n = 3
 Output ：3
 explain ： There are three ways to climb to the top .
1. 1  rank  + 1  rank  + 1  rank 
2. 1  rank  + 2  rank 
3. 2  rank  + 1  rank 
 

 Tips ：

1 <= n <= 45

     
      1.
      2.
      3.
      4.
      5.
      6.
      7.
      8.
      9.
      10.
      11.
      12.
      13.
      14.
      15.
      16.
      17.
      18.
      19.
      20.
      21.
      22.
      23.
      24.

Climbing stairs can also be seen as a fiboracci sequence in essence ：

class Solution:
    def numWays(self, n: int) -> int:
        if n == 0 or n == 1:
            return 1

        dp = [0] * (n + 1) 
        dp[0] = 1   # 0  There are steps  1  Kind of   Method 
        dp[1] = 1   # 1  There are steps  1  Methods 
    

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

        return dp[n] % 1000000007

     1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.

3. Different paths

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 ？

 Example  1：

 Input ：m = 3, n = 7
 Output ：28
 Example  2：

 Input ：m = 3, n = 2
 Output ：3
 explain ：
 From the top left corner , All in all  3  Path to the bottom right .
1.  towards the right  ->  Down  ->  Down 
2.  Down  ->  Down  ->  towards the right 
3.  Down  ->  towards the right  ->  Down 
 Example  3：

 Input ：m = 7, n = 3
 Output ：28
 Example  4：

 Input ：m = 3, n = 3
 Output ：6
 
 Tips ：

1 <= m, n <= 100
 Question data guarantee that the answer is less than or equal to  2 * 109

     
      1.
      2.
      3.
      4.
      5.
      6.
      7.
      8.
      9.
      10.
      11.
      12.
      13.
      14.
      15.
      16.
      17.
      18.
      19.
      20.
      21.
      22.
      23.
      24.
      25.
      26.
      27.
      28.
      29.
      30.
      31.
      32.

Answer 1 ：

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

        def diff_path(row, col):

            #  Any cell in the first column , Only the method from its previous cell 
            for i in range(n):
                dp[0][i] = 1

            #  Any cell in the first row , There is only one way to come from its previous cell 
            for j in range(m):
                dp[j][0] = 1

            #  Any cell has two paths from the top or left , first line 、 The first column is populated , No more filling 
            for i in range(1, row):
                for j in range(1, col):
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1]

                #  Returns the position of the last cell 
            return dp[row - 1][col - 1]

        return diff_path(m, n)

     1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.

Explanation 2 ：（ Easier to understand ）

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

        for row in range(m):
            for col in range(n):
                #  The first lattice has only one way 
                if row == 0 and col == 0:
                    dp[row][col] = 1
                elif col == 0:
                    #  Any cell in the first row , There is only one way to come from its previous cell 
                    dp[row][col] = dp[row-1][col]    
                elif row == 0:  
                    #  Any cell in the first column , Only the method from its previous cell 
                    dp[row][col] = dp[row][col - 1]     
                else:
                    #  Other situations （ middle ）： Any cell has a robot from its left or top 
                    dp[row][col] = dp[row - 1][col] + dp[row][col - 1]  


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

     1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.

4. Different paths II

63. Different paths II

 Example  1：

 Input ：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
 Output ：2
 explain ：3x3  There is an obstacle in the middle of the grid .
 From the top left corner to the bottom right corner, there are  2  Different paths ：
1.  towards the right  ->  towards the right  ->  Down  ->  Down 
2.  Down  ->  Down  ->  towards the right  ->  towards the right 


 Example  2：

 Input ：obstacleGrid = [[0,1],[0,0]]
 Output ：1
 
 Tips ：

m == obstacleGrid.length
n == obstacleGrid[i].length
1 <= m, n <= 100
obstacleGrid[i][j]  by  0  or  1

     
      1.
      2.
      3.
      4.
      5.
      6.
      7.
      8.
      9.
      10.
      11.
      12.
      13.
      14.
      15.
      16.
      17.
      18.
      19.
      20.
      21.

Answer key ：

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        row = len(obstacleGrid)
        col = len(obstacleGrid[0])

        #  There's only one cell , That is, one row and one column 
        if row == 1 and col == 1:
            if obstacleGrid[0][0] == 1:
                return 0
            else:
                return 1

        dp = [[0] * col for i in range(row)]

        for i in range(row):
            for j in range(col):
                #  Encounter obstacles , Skip the current loop 
                if obstacleGrid[i][j] == 1:
                    continue

                if i == 0 and j == 0:
                    dp[i][j] = 1
                elif i == 0:
                    dp[i][j] = dp[i][j - 1]
                elif j == 0:
                    dp[i][j] = dp[i - 1][j]
                else:
                    dp[i][j] = dp[i][j - 1] + dp[i - 1][j]

        return dp[row - 1][col - 1]

     1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.

5. Minimum path sum

64. Minimum path sum

 Given a... That contains a nonnegative integer  m x n  grid  grid , Please find a path from the top left corner to the bottom right corner , Make the sum of the numbers on the path the smallest .

 explain ： You can only move down or right one step at a time .

 Example  1：

 Input ：grid = [[1,3,1],[1,5,1],[4,2,1]]
 Output ：7
 explain ： Because the path  1→3→1→1→1  The sum of is the smallest .
 Example  2：

 Input ：grid = [[1,2,3],[4,5,6]]
 Output ：12
 
 Tips ：

m == grid.length
n == grid[i].length
1 <= m, n <= 200
0 <= grid[i][j] <= 100

     
      1.
      2.
      3.
      4.
      5.
      6.
      7.
      8.
      9.
      10.
      11.
      12.
      13.
      14.
      15.
      16.
      17.
      18.
      19.
      20.

Answer key ：

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])

        #  When there is only one cell 
        if m == 1 and n == 1:
            return grid[0][0]

        dp = [[0] * n for i in range(m)]

        for i in range(m):
            for j in range(n):
                
                if i == 0:
                    #  first line , and  =  Current cell number  +  The previous cell number 
                    dp[i][j] = dp[i][j - 1] + grid[i][j]
                elif j == 0:
                    #  First column , and  =  Current cell number  +  Previous cell number 
                    dp[i][j] = dp[i - 1][j] + grid[i][j]
                else:
                    #  Middle cell , and  =  Current cell number  +  The smallest number in the previous and previous cells 
                    dp[i][j] = min(dp[i][j - 1], dp[i - 1][j]) + grid[i][j]

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

     1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.

Be careful ：dp[i][j - 1]、dp[i - 1][j] It represents state transition , It includes the sum of the previous paths , and grid[i][j] Represents only a number in the current cell , So it is ：dp[i][j] = dp[i][j - 1] + grid[i][j], instead of dp[i][j] = grid[i][j - 1] + grid[i][j]

原网站

版权声明
本文为[51CTO]所创，转载请带上原文链接，感谢
https://yzsam.com/2022/178/202206271233069915.html