当前位置：首页 > news >正文

面试算法高频08-动态规划-01

news 来源：原创 2025/8/19 20:29:53

动态规划

递归知识要点

递归代码模板：提供递归代码的标准形式public void recur(int level, int param) ，包含终止条件（if (level> MAX_LEVEL)）、当前层逻辑处理（process(level, param)）、向下一层递归（recur(level: level +1, newParam)）以及状态恢复（未完整代码呈现，但为重要环节），强调对该模板的记忆有助于构建递归算法逻辑。
递归状态树：递归状态树展示了问题逐步分解为子问题再求解的层级结构，直观呈现递归过程中各子问题间的关系，辅助理解递归算法的执行流程与问题处理机制。
人肉递归的问题及解决思路：人肉递归存在效率低、易出错的问题，人脑记忆的局限性使得在处理多层递归（如第三、四层）时难度加大。解决方法是寻找最近最简的方法，将问题拆解为可重复解决的子问题，运用数学归纳法思维，挖掘问题中的重复性，转化为计算机指令解决，避免过度依赖人肉递归。

动态规划知识要点

定义：动态规划是一种数学优化方法和计算机编程方法，由Richard Bellman在20世纪50年代提出。其核心是通过递归方式把复杂问题分解为简单子问题来简化求解过程，具有“分治 + 最优子结构”的特点，在多个领域广泛应用。
与递归、分治的关系：动态规划与递归、分治既有共性又有差异。共性在于都要找出重复子问题；差异在于动态规划具有最优子结构，并且在求解过程中能够淘汰次优解，从而提高算法效率，普通递归或分治可能不具备这些特性。
实例分析：以Fib(6)状态树为例，其中存在许多重复子状态（如f(4)、f(3)、f(2)多次出现）。利用动态规划淘汰次优解，可优化计算过程、避免重复计算，但可能使时间复杂度变为 $n^2$ ，实际应用时需要权衡算法性能与复杂度。

题目练习

题目描述

使用动态规划（Dynamic Programming）方法求解斐波那契数列（Fibonacci Sequence）的第 n 项。斐波那契数列的定义为：

F(0) = 0
F(1) = 1
F(n) = F(n-1) + F(n-2)（当 n ≥ 2 时）

分析思路

1. 动态规划核心思想

斐波那契数列具有最优子结构和重叠子问题，适合用动态规划求解：

最优子结构：F(n) 由 F(n-1) 和 F(n-2) 唯一确定。
重叠子问题：递归求解时，F(n-1) 和 F(n-2) 会被重复计算（如计算 F(6) 时，F(4) 会被计算两次）。动态规划通过存储中间结果避免重复计算，提升效率。

2. 状态定义

定义 dp[i] 表示斐波那契数列的第 i 项的值。

3. 状态转移方程

根据斐波那契数列定义，状态转移方程为：
[ dp[i] = dp[i-1] + dp[i-2] ]
初始条件：

dp[0] = 0
dp[1] = 1

4. 空间优化

常规动态规划需用数组存储所有中间状态（空间复杂度 O(n)），但由于 dp[i] 仅依赖前两项 dp[i-1] 和 dp[i-2]，可通过两个变量 prev1（存储 F(n-2)）和 prev2（存储 F(n-1)）迭代更新，将空间复杂度优化至 O(1)。

最优解答（Python）

方法一：常规动态规划（数组存储中间状态）

def fib(n: int) -> int:if n <= 1:return ndp = [0] * (n + 1)dp[0], dp[1] = 0, 1for i in range(2, n + 1):dp[i] = dp[i-1] + dp[i-2]return dp[n]

方法二：空间优化动态规划（`O(1)` 空间）

def fib(n: int) -> int:if n <= 1:return nprev1, prev2 = 0, 1  # 对应 F(0) 和 F(1)for i in range(2, n + 1):current = prev1 + prev2  # 计算 F(i)prev1, prev2 = prev2, current  # 迭代更新前两项return prev2  # 最终 prev2 存储 F(n)

复杂度分析

时间复杂度：两种方法均为 O(n)，每个状态仅计算一次。
空间复杂度：
- 方法一为 O(n)（存储数组 dp）。
- 方法二为 O(1)（仅用两个变量迭代）。

关键点

状态转移方程：明确子问题之间的关系，是动态规划的核心。
边界条件：正确初始化 dp[0] 和 dp[1]，避免逻辑错误。
空间优化：利用问题特性（仅依赖前两项），减少内存占用，提升效率。

示例验证

当 n = 6 时：

常规方法：dp[2]=1, dp[3]=2, dp[4]=3, dp[5]=5, dp[6]=8，返回 8。
优化方法：通过迭代计算，最终 prev2 为 8，结果一致。

通过动态规划，斐波那契数列的求解效率从递归的指数级（O(2^n)）提升至线性级（O(n)），是重叠子问题和最优子结构的经典应用。

题目描述（课件中的路径计数问题）

在一个 m×n 的网格 中，从左上角起点 (0, 0) 移动到右下角终点 (m-1, n-1)，每次只能 向下（Row+1）或向右（Col+1） 移动一步。网格中某些单元格为 障碍物（非空地），若单元格 (i,j) 是障碍物，则无法通过。求从起点到终点的 路径总数。

网格路径示意图

在这里插入图片描述

最优解答（Python）

def count_paths(grid: list[list[bool]]) -> int:m, n = len(grid), len(grid[0])dp = [[0] * n for _ in range(m)]dp[m-1][n-1] = 1 if not grid[m-1][n-1] else 0for i in range(m-1, -1, -1):for j in range(n-1, -1, -1):if i == m-1 and j == n-1:continueif grid[i][j]:dp[i][j] = 0continuedown = dp[i+1][j] if i+1 < m else 0right = dp[i][j+1] if j+1 < n else 0dp[i][j] = down + rightreturn dp[0][0]# 示例测试
if __name__ == "__main__":grid = [[False, False, False],[False, False, False],[False, False, False]]print(count_paths(grid))  # 输出: 6

答案解析

1. 动态规划核心思路（课件要点）

状态定义：dp[i][j] 表示从 (i,j) 到终点的路径数，障碍物单元格路径数为 0。
状态转移：dp[i][j] = dp[i+1][j] + dp[i][j+1]（下方和右方路径数之和），与课件中“累加关系”的状态转移方程一致。
倒推计算：从终点向上、向左递推，避免起点边界特殊处理，符合课件中“从最下面依次往上”的思路。

2. 复杂度与关键点

时间/空间复杂度均为 O(m×n)，通过二维数组存储中间状态，确保每个单元格仅计算一次。
障碍物判断直接决定当前单元格路径数是否为 0，是课件中“if a[i,j]=‘空地’”条件的代码实现。

该解答结合课件核心思想与图片可视化，清晰呈现动态规划在路径计数问题中的应用。

动态规划

递归知识要点

动态规划知识要点

题目练习

题目描述

分析思路

1. 动态规划核心思想

2. 状态定义

3. 状态转移方程

4. 空间优化

最优解答（Python）

方法一：常规动态规划（数组存储中间状态）

方法二：空间优化动态规划（O(1) 空间）

复杂度分析

关键点

示例验证

题目描述（课件中的路径计数问题）

网格路径示意图

最优解答（Python）

答案解析

1. 动态规划核心思路（课件要点）

2. 复杂度与关键点

相关文章：

方法二：空间优化动态规划（`O(1)` 空间）