题单介绍
DP 把问题拆成子问题,用数组记下答案避免重复。先定义状态,再写转移与边界。
学习目标
- 能定义 dp 数组含义
- 掌握线性 DP、背包与 LIS/LCS 基本转移
- 先写边界 dp[0]、dp[1],再循环转移
- 背包内层循环方向决定 01 还是完全
- 题解只给思路与步骤,请自己实现代码
阶段安排(共 27 题)
1. DP基础(11 题)
上台阶、数列等一维转移。
2. DP进阶(7 题)
更多约束或二维状态。
3. 背包基础(6 题)
01 / 完全背包模板。
4. LIS和LCS(6 题)
最长上升 / 最长公共子序列。
使用建议
01
前缀最大值
入门
--
练习
02
前缀最小值
入门
--
练习
03
跳格子
入门
--
练习
04
跳格子2
入门
--
练习
05
最大部分和(连续部分和)
基础
--
练习
06
取数
基础
--
练习
07
最长不下降子序列(LIS)
基础
--
练习
08
合唱队形求解
基础
--
练习
09
拦截导弹
基础
--
练习
10
数塔问题
基础
--
练习
11
简单背包问题
入门
--
练习
12
传球游戏
基础
--
练习
13
房屋积水
提高
--
练习
14
挖地雷的算法
基础
--
练习
15
机器分配
提高
--
练习
16
乌龟棋
基础
--
练习
17
奶牛沙盘队
基础
--
练习
18
小朋友的数字
提高
--
练习
19
采灵芝
基础
--
练习
20
多重背包(1)
基础
--
练习
21
多重背包(2)
提高
--
练习
22
混合背包
提高
--
练习
23
环游世界之背包问题
入门
--
练习
24
最长上升子序列LIS(2)
提高
--
练习
25
最长公共子序列(LCS)(1)
基础
--
练习
26
最长公共子序列(LCS)(2)
提高
--
练习
27
最少的修改次数
提高
--
练习