讲解前缀和的定义、构造与区间查询方法,并应用于多种子数组求和问题。
2020年7月4日 · 3201 字
讲解前缀和的定义、构造与区间查询方法,并应用于多种子数组求和问题。
对比三道换硬币问题,讲清最少硬币数、组合数与排列数对应的动态规划建模差异。
把股票买卖系列建模为状态机,系统推导多种交易限制下的动态规划状态与转移。
通过多类动态规划题目,讲解如何选择状态、拆分子问题并梳理状态间依赖。
以最大子数组和等问题为例,讲解如何定义以特定位置结尾的子数组子问题。
从递归子问题出发推导编辑距离的二维动态规划状态、转移方程与操作顺序优化。
动态规划求的不只是最大值或最小值。本文以打家劫舍和最长公共子序列为例,讲解如何使用 back 数组从 DP 结果恢复具体的最优解。
以最长公共子序列为例,讲解二维动态规划的子问题定义、递推关系与空间优化。
以打家劫舍为例,归纳定义子问题、写递推式、确定顺序和空间优化四个步骤。
对比 DFS 与 BFS,讲解层序遍历、最短路径和多源 BFS 等典型使用场景。