当前位置：网站首页>动态规划

动态规划

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

1. 斐波那契数列

斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：

F(0) = 0，F(1) = 1
F(n) = F(n - 1) + F(n - 2)，其中 n > 1
给定 n ，请计算 F(n) 。

示例 1：

输入：n = 2
输出：1
解释：F(2) = F(1) + F(0) = 1 + 0 = 1
示例 2：

输入：n = 3
输出：2
解释：F(3) = F(2) + F(1) = 1 + 1 = 2
示例 3：

输入：n = 4
输出：3
解释：F(4) = F(3) + F(2) = 2 + 1 = 3
 
提示：

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.

题解：

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

        if n == 1:
            return 1

        dp = [0] * (n + 1)  # 定义 dp 数组
        dp[0] = 0   # 初始化
        dp[1] = 1

        for i in range(2, n+1):
            dp[i] = dp[i - 1] + dp[i - 2]   # 递推公式

        return dp[n]

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

2. 爬楼梯

70. 爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

示例 1：

输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶
示例 2：

输入：n = 3
输出：3
解释：有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶
 

提示：

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.

爬楼梯实质上也可以看作一个斐波拉契数列：

类似题目剑指 Offer 10- II. 青蛙跳台阶问题：

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

        dp = [0] * (n + 1) 
        dp[0] = 1   # 0 个台阶有 1 种 方法
        dp[1] = 1   # 1 个台阶有 1 种方法
    

        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. 不同路径

62. 不同路径

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

问总共有多少条不同的路径？

示例 1：

输入：m = 3, n = 7
输出：28
示例 2：

输入：m = 3, n = 2
输出：3
解释：
从左上角开始，总共有 3 条路径可以到达右下角。
1. 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右
3. 向下 -> 向右 -> 向下
示例 3：

输入：m = 7, n = 3
输出：28
示例 4：

输入：m = 3, n = 3
输出：6
 
提示：

1 <= m, n <= 100
题目数据保证答案小于等于 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.

题解一：

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

            # 第一列的任意单元格，只有来自它上一个单元格过来的方法
            for i in range(n):
                dp[0][i] = 1

            # 第一行的任意单元格，只有来自它前一个单元格过来的一种方法
            for j in range(m):
                dp[j][0] = 1

            # 随意一个单元格有来自上或者左的两种路径，第一行、第一列已填充，不用继续填充
            for i in range(1, row):
                for j in range(1, col):
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1]

                # 返回最后一个单元格的位置
            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.

题解二：（更容易理解）

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):
                # 第一个格子只有一种方法
                if row == 0 and col == 0:
                    dp[row][col] = 1
                elif col == 0:
                    # 第一行的任意单元格，只有来自它前一个单元格过来的一种方法
                    dp[row][col] = dp[row-1][col]    
                elif row == 0:  
                    # 第一列的任意单元格，只有来自它上一个单元格过来的方法
                    dp[row][col] = dp[row][col - 1]     
                else:
                    # 其他情况（中间）：任意一个单元格有来自其左或上两个方向的机器人
                    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. 不同路径 II

63. 不同路径 II

示例 1：

输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
输出：2
解释：3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径：
1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右


示例 2：

输入：obstacleGrid = [[0,1],[0,0]]
输出：1
 
提示：

m == obstacleGrid.length
n == obstacleGrid[i].length
1 <= m, n <= 100
obstacleGrid[i][j] 为 0 或 1

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

题解：

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

        # 只有一个单元格，即一行一列时
        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):
                # 遇到阻碍，就跳过当前循环
                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. 最小路径和

64. 最小路径和

给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。

示例 1：

输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7
解释：因为路径 1→3→1→1→1 的总和最小。
示例 2：

输入：grid = [[1,2,3],[4,5,6]]
输出：12
 
提示：

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.

题解：

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

        # 只有一个单元格时
        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:
                    # 第一行，和 = 当前单元格数字 + 前一个单元格数字
                    dp[i][j] = dp[i][j - 1] + grid[i][j]
                elif j == 0:
                    # 第一列，和 = 当前单元格数字 + 上一个单元格数字
                    dp[i][j] = dp[i - 1][j] + grid[i][j]
                else:
                    # 中间单元格，和 = 当前单元格数字 + 上一个和前一个单元格中最小的数字
                    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.

注意：dp[i][j - 1]、dp[i - 1][j] 代表的是状态转移，它包括前面走过的路径之和，而 grid[i][j] 代表的仅仅只是当前单元格一个数字，所以是：dp[i][j] = dp[i][j - 1] + grid[i][j]，而不是 dp[i][j] = grid[i][j - 1] + grid[i][j]

原网站

版权声明
本文为[51CTO]所创，转载请带上原文链接，感谢
https://blog.51cto.com/u_13942374/5419012