数据结构与算法之动态规划

作者： 千石 支持：点赞、收藏、评论 欢迎各位在评论区交流

前言

本文内容来自我平时学习的一些积累，如有错误，还请指正

在题目实战部分，我将代码实现和代码解释设置在了解题思路的下方，方便各位作为参考刷题

一些话

本文内容来自我平时学习的一些积累，如有错误，还请指正

在题目实战部分，我将代码实现和代码解释设置在了解题思路的下方，方便各位作为参考刷题

题目练习步骤：

1. 给自己10分钟，读题并思考解题思路
2. 有了思路以后开始写代码，如果在上一步骤中没有思路则停止思考并且看该题题解
3. 在看懂题解（暂时没看懂也没关系）的思路后，背诵默写题解，直至能熟练写出来
4. 隔一段时间，再次尝试写这道题目

前置知识

动态规划是一种解决最优化问题的算法。它通过将原问题划分为若干个子问题，然后从子问题到原问题依次递推，从而得到最终结果。

动态规划的主要实现关键点如下：

1. 状态转移：该步骤定义了通过当前状态如何转移到下一个状态。

2. 状态存储：该步骤定义了如何存储当前状态以便在以后的转移中使用。

3. 状态初始化：该步骤定义了如何初始化问题的起始状态。

4. 边界处理：该步骤定义了在达到边界条件时该如何处理状态。

5. 状态重复：该步骤定义了如何避免状态重复计算。

动态规划是一种非常有效的解决优化问题的算法，但是它需要对问题有一定的理解和分析。如果不理解动态规划的基本原理，很难正确地实现该算法。

题目

题目一：62. 不同路径

思路

我们可以用一个二维数组 dp 来存储每一个点到终点的不同路径数。从终点的点开始，将该点设为1，然后分别更新该点上方和左边的点的路径数，即 dp[i][j] = dp[i][j-1] + dp[i-1][j]。最终，我们可以返回 dp[m-1][n-1]，它表示到网格的右下角的不同路径数。

代码实现

def uniquePaths(m, n):
    dp = [[0] * 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][j-1] + dp[i-1][j]
    return dp[m-1][n-1]

复杂度分析

我们只需要更新网格中的所有点一次，因此时间复杂度为 O(mn)。空间复杂度为 O(mn)，因为我们需要存储每一个点到终点的不同路径数。

结果展示

题目二：63. 不同路径 II

思路

我们可以用一个二维数组 dp 来存储每一个点到终点的不同路径数。如果一个点是障碍物，那么我们就将它的路径数设为0，否则它的路径数是从该点上方和左边的点的路径数之和，即 dp[i][j] = dp[i][j-1] + dp[i-1][j]。最终，我们可以返回 dp[m-1][n-1]，它表示到网格的右下角的不同路径数。

代码展示

def uniquePathsWithObstacles(obstacleGrid):
    m, n = len(obstacleGrid), len(obstacleGrid[0])
    dp = [[0] * n for _ in range(m)]
    dp[0][0] = 1 - obstacleGrid[0][0]
    for i in range(1, m):
        dp[i][0] = dp[i-1][0] * (1 - obstacleGrid[i][0])
    for j in range(1, n):
        dp[0][j] = dp[0][j-1] * (1 - obstacleGrid[0][j])
    for i in range(1, m):
        for j in range(1, n):
            if obstacleGrid[i][j] == 1:
                dp[i][j] = 0
            else:
                dp[i][j] = dp[i][j-1] + dp[i-1][j]
    return dp[m-1][n-1]

复杂度分析

我们只需要更新网格中的所有点一次，因此时间复杂度为 O(mn)。空间复杂度为 O(mn)，因为我们需要存储每一个点到终点的不同路径数。

结果展示

题目三：剑指 Offer II 095. 最长公共子序列

思路

把大问题分解为若干个子问题，解决每一个子问题，组合成原问题的解。我们可以用一个二维的数组 dp[i][j] 表示 text1 的前 i 个字符与 text2 的前 j 个字符的最长公共子序列的长度。

状态转移方程如下：

• 如果 text1[i] == text2[j]，那么 dp[i][j] = dp[i-1][j-1] + 1
• 如果 text1[i] != text2[j]，那么 dp[i][j] = max(dp[i-1][j], dp[i][j-1])

代码展示

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        m, n = len(text1), len(text2)
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if text1[i-1] == text2[j-1]:
                    dp[i][j] = dp[i-1][j-1] + 1
                else:
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1])
        return dp[m][n]

复杂度分析

算法的时间复杂度为 O(m * n)，其中 m 和 n 分别为 text1 和 text2 的长度。

结果展示