Normalization

Posted on Edited on Views:

1、线性 DP

2、区间 DP

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

3、背包 DP

416. 分割等和子集 (01背包-要求恰好取到背包容量)
494. 目标和 (01背包-求方案数)
322. 零钱兑换 (完全背包)

518. 零钱兑换 II (完全背包-求方案数)
474. 一和零 (二维费用背包)

4、树形 DP

124. 二叉树中的最大路径和
1245. 树的直径 (邻接表上的树形DP)
543. 二叉树的直径
333. 最大 BST 子树
337. 打家劫舍 III

5、状态压缩 DP

464. 我能赢吗
526. 优美的排列
935. 骑士拨号器
1349. 参加考试的最大学生数

6、数位 DP

233. 数字 1 的个数
902. 最大为 N 的数字组合
1015. 可被 K 整除的最小整数

7、计数型 DP

计数型DP都可以以组合数学的方法写出组合数，然后dp求组合数
62. 不同路径
63. 不同路径 II

96. 不同的二叉搜索树 (卡特兰数)
1259. 不相交的握手 (卢卡斯定理求大组合数模质数)

8、递推型 DP

所有线性递推关系都可以用矩阵快速幂做，可以O(logN)，最典型是斐波那契数列70. 爬楼梯
509. 斐波那契数
935. 骑士拨号器

957. N 天后的牢房
1137. 第 N 个泰波那契数

9、概率型 DP

求概率，求数学期望
808. 分汤
837. 新21点

10、博弈型 DP

策梅洛定理，SG 定理，minimax

剑指 Offer 46. 把数字翻译成字符串

剑指 Offer 49. 丑数

1240. 铺瓷砖

1、算法题：最长不重复字串

算法：堆排序、栈实现队列、反转链表

算法：字符串反转 、 倒着打印链表（为什么用递归比用栈差？） 、 单例模式

  1. 算法题：数组A和数组B，求 A并B - A交B；（说了几种，好像不满意不是最优解）
  2. 算法题：矩阵搜索（说完之后问优化，没想到，提示二分搜索）；
  3. 算法题：手写堆排序
  4. 算法题： 实现一个四则运算计算器（两个栈 + 优先级） ， 冒泡排序
  5. 算法题：二分搜索相关
  6. 算法：实现一个缓存队列 ，二叉树的镜像
  7. 算法题： （1）树的节点最大距离（2）区间覆盖 例 [1 3] [2 5] [3 6]能否覆盖[2 6]