第七周 动态规划

题目数：21

本周作业

• 完全平方数

（Medium）

要求：完全平方数看作物品，体积为 n，价值为 1，用背包 DP 的思想解题

半年内出题频次：

• 跳跃游戏

（Medium）半年内出题频次：

• 跳跃游戏 II

（Medium）

要求：用动态规划解题，并与之前的贪心解法做对比

半年内出题频次：

• 最长回文子序列

（Medium）半年内出题频次：

• 二叉树中的最大路径和

（Hard）半年内出题频次：

实战例题

以下为课上实战例题

第 13 课 动态规划（二）

买卖股票系列问题

股票问题系列通解

• 买卖股票的最佳时机

（Easy）半年内出题频次：

• 买卖股票的最佳时机 II

（Easy）半年内出题频次：

• 买卖股票的最佳时机 III

（Easy）半年内出题频次：

• 买卖股票的最佳时机 IV

（Hard）半年内出题频次：

• 买卖股票的最佳时机含手续费

（Medium）半年内出题频次：

• 最佳买卖股票时机含冷冻期

（Medium）半年内出题频次：

线性 DP 问题

• 打家劫舍

（Medium）半年内出题频次：

• 打家劫舍 II- 环形 DP

（Medium）半年内出题频次：

• 编辑距离（重点题）

（Hard）半年内出题频次：

背包问题

• 分割等和子集

（Medium）半年内出题频次：

• 零钱兑换 II

（Medium）半年内出题频次：

第 14 课 动态规划（三）

动态规划的优化

• 满足不等式的最大值

（Hard）半年内出题频次：

• 环形子数组的最大和

（Medium）半年内出题频次：

区间动态规划

• 戳气球 （Hard）半年内出题频次：

• 合并石头的最低成本（选做）

（Hard）半年内出题频次：

树形动态规划

• 打家劫舍 III

（Medium）半年内出题频次：