动态规划：经典题目汇总_动态规划十大经典题目

动态规划：经典题目汇总

一、动态规划的定义

动态规划（动态递推）：Dynamic Programing

• 找重复性
• 最优子结构
• 数学归纳

关键点：

• 和递归、分治没有根本区别（关键看有没有最优子结构）；
• 共性：找到重复子问题；
• 差异性：最优子结构、中途可以淘汰次优解；

动态规划：

• 重复子问题、最优子结构
• 存储中间状态：dp
• 递推公式

二、经典例题

3.1 一维的DP：斐波那契数列、使用最小花费爬楼梯

• 递归
• 记忆化搜索：递归+缓存
• DP：自底向上

爬楼梯及扩展题目

3.2 二维的DP：不同路径1、不同路径2、最小路径和

• 分治+记忆化搜索

不同路径1、2、最小路径和

3.3 字符串变化的DP：最长公共子序列

字符串DP：最长公共子序列

三、动态规划实战题目

3.1 爬楼梯

延伸：

1. 一次可以走1、2、3阶台阶；
2. 一次可以走[1、2、3、4、5…]阶台阶；
3. 相邻两步的步伐不能相同；
4. 使用最小花费爬楼梯；

爬楼梯及扩展题目

3.2 最小路径和

• DP方法
• 递归+缓存

动态规划：最小路径和

3.3 最大子序列和、乘积最大子序列

动态规划：最大子序列和、乘积最大子序列

3.4 零钱兑换（和爬楼梯问题有异曲同工之妙）

• 方法一：暴力求解
• 方法二：BFS
• 方法三：DP

动态规划：零钱兑换

3.5 打家劫舍1、打家劫舍2、打家劫舍3

• dp[i][0]
• dp[i]
• m、n

打家劫舍1、2

3.6 股票买卖问题

股票买卖的六道经典问题

四、高阶的动态规划

4.1 复杂度来源

• 状态维度：更多维度
• 状态转移方程：方程更复杂

4.2 编辑距离

• BFS、双端BFS
• DP

编辑距离

五、其他题目

5.1 最长上升子序列

5.2 解码方法

5.3 最长有效括号

5.4 最大矩形

5.5 不同的子序列

5.6 赛车

其他题目