dp分类

Catalogue

1. 1. 线性dp
2. 2. 区间dp
3. 3. 背包dp
4. 4. 树形dp
5. 5. 状态压缩
6. 6. 数位
7. 7. 计数型
8. 8. 递推型
9. 9. 概率型
10. 10. 博弈型
11. 11. 记忆化搜索

参考资料

线性dp

• 最经典单串:最长上升子序列
• 最经典双串:最长公共子序列
• 三角形最小路径和
• 乘积最大子数组
• 鸡蛋掉落
• 信封问题
• 打家劫舍系列
  • 打家劫舍
  • 打家劫舍II
• 股票系列
  • 买卖股票的最佳时机
  • 买卖股票的最佳时机II
  • 买卖股票的最佳时机III
  • 买卖股票的最佳时机IV
  • 买卖股票的最佳时机含手续费
  • 买卖股票的最佳时机含冷冻期
• 字符串匹配系列
  • 编辑距离
  • 通配符匹配
  • 正则表达式匹配

区间dp

• 最长回文子序列
• 统计不同回文子字符串
• 多边三角形剖分的最低得分
• 奇怪的打印机
• 戳气球

背包dp

• 分割等和子集
• 目标和
• 零钱兑换
• 零钱兑换II
• 一和零

树形dp

• 二叉树的最大路径和
• 树的直径
• 二叉树的直径
• 最大bst树
• 打家劫舍III

状态压缩

• 我能赢吗
• 优美的排列
• 骑士拨号器
• 参加考试的最大学生数

数位

• 数字一的个数
• 最大为N的数字组合
• 可被k整除的最小整数

计数型

• 不同路径
• 不同路径II
• 不同的二叉搜索数
• 不相交的握手

递推型

• 爬楼梯
• 斐波那契数
• 骑士拨号器
• N天后的牢房
• 第N个斐波那契数

概率型

• 分汤
• 新21点

博弈型

• 翻转游戏
  • 翻转游戏
  • 翻转游戏II
• nim游戏
  • nim游戏
• 石子游戏
  • 石子游戏
  • 石子游戏II
• 井字游戏
  • 判定井字棋胜负
  • 有效的井字棋
  • 找出井字棋的胜者

记忆化搜索

• 矩阵中的最长递增路径
• 出界的路径数

参考资料