数位统计DP (y总翻车标点(x))
计树问题：
给定两个整数 a 和 b，求 a 和 b 之间的所有数字中 0∼9 的出现次数。

利用前缀和思想：
需要实现一个count(n, x)表示1 - n种x出现的次数
res = count(b, x) - count(a - 1, x)

如何求count(n, x)？
    分情况讨论(以x = 1为例) 分别求出1在每一位上出现的次数

    count(abcdefg, 1) = 
        即1在每一位上出现的次数
        简单分析可知1在其中一位出现的次数的求法都差不多，不妨试求一下1在第4位上出现的次数
        即 1 <= xxx1yyy <= abcdefg情况：
        (1) xxx > abc, 则xxx1yyy 必大于abcdefg, =0 不可能
        2) xxx = 000 - abc - 1, 则xxx1yyy必< abcdefg, yyy可取000 - 999，共abc * 1000方案数
        3) xxx = abc
            3.1) d < 1, xxx1yyy > abc0efg无解，0种方案 不可能
            3.2) d = 1, yyy取000-efg的时候保证满足xxx1yyy <= abcdefg，共计efg + 1种方案
            3.3) d > 1, yyy 取000 - 999时候保证满足xxx1yyy <= abcdefg，共计1000种方案

        count()函数怎么调?
            先想个暴力求法，再和dp比对

        边界情况：当d = ?
        1. 当1出现在第1位时，2)不存在。只用算3)即可 
        2. 当x = 0时，2)最高位不能取000，因为前导0的数字不是合法数字；x应该为001 - abc - 1, yyy可取000 - 999,  3)又在x = 0时不存在

蒙德里安的梦想 状态压缩经典应用
状态压缩：将一个整数状态看作二进制方式的dp

求把 N×M 的棋盘分割成若干个 1×2 的长方形，有多少种方案。

分析：
    转化为在n * m格子里放 1 * 2小方格的方案

    摆放方块时先放横向的，再放纵向的（易得横向全摆完后，竖向也只能把剩余位置填充进去）

    因此，总方案数 = 仅横向合法的放置小方块的方案数

    那如何判断当前方案是否合法呢？即对所有剩余位置，能否填充满竖向小方块？
        按列枚举，每一列内部所有连续的空着的小方块，需要是偶数个(1 * 2小方块竖向长度为2，偶数必能填满，奇数不行)

动态规划：

    [视频讲解](https://www.acwing.com/video/556/)

    化零为整（状态表示），化整为零（状态计算）

    状态表示: 
        f[i, j] 表示已经前i-1列摆好1*2小方块，且从第i-1列，伸出(横向小方块跨列)到第i列的状态是j的所有方案
    j可以用二进制数表示，记跨列为1，否则0; 但用十进制存二进制数

    状态计算：
        集合分割一般按最后一步操作分割
        最后一步操作：从i - 2到i - 1列都有哪些行放的是 1*2 的小方格

        分割成 2 ^ 行数 个子集

        对于其中一个子集从i - 2到i - 1的状态为k，当前从i - 1到i的状态为j：
            方案数: f[i - 1, k](每一个小集合方案数) && 合法(
                1. j与k不能在同一行 = 1: j & k == 0（否则与1 * 2小方格设定冲突）
                2. i-1列空着的位置完全固定，需满足空的位置被塞满 (j | k不存在连续奇数个0)
            )
        加和所有方案数
        res = f[m, 0]

    时间复杂度较高

    优化版：
        先预处理每个状态j而言有哪些状态能更新到j

最短哈密尔顿路径：
给定一张 n 个点的带权无向图，点从 0∼n−1 标号，求起点 0 到终点 n−1 的最短 Hamilton 路径。
Hamilton 路径的定义是从 0 到 n−1 不重不漏地经过每个点恰好一次。

状态表示f[i, j]: 集合：所有从0走到j，且走过的所有点是i的所有路径
i为二进制数，每一位表示当前点是否走过
                 属性： Min

状态计算： 
    集合划分：根据i的倒数第二个点(k)分类，分为：倒数第二个点为0， 1， 2， ... , n - 1
    0 -> k -> j: k -> j 为题目中给定的边，要使路径最短，缩短0 -> k
    o -> k : i - {j} 即 i - (1 << j) (即从k走到j时，将点j走过的位置由1变为0)
    min(0 -> k -> j): min(f(i - {j}, k) + akj)

树形DP
没有上司的舞会:
Ural大学有N名职员，编号为1~N。

    他们的关系就像一棵以校长为根的树，父节点就是子节点的直接上司。

    每个职员有一个快乐指数，用整数 Hi 给出，其中 1≤i≤N。

    现在要召开一场周年庆宴会，不过，没有职员愿意和直接上司一起参会。

    在满足这个条件的前提下，主办方希望邀请一部分职员参会，使得所有参会职员的快乐指数总和最大，求这个最大值。

ps: 相比线性dp, 背包问题思维跨度很高，接受后难度不高

状态表示:
    f[u, 0]: 表示所有以u为根的子树中选择,并且不选u这个点的方案的幸福值
    f[u, 1]: 表示所有以u为根的子树中选择, 并且选择u这个点的方案的幸福值

    属性: max

状态计算:
 f[u, 0]: 由于这种情况为不选u，所以所有子树的最大值即为所求: f[u, 0]  = SUM(max(f[si, 0), f(si, 1))
 f[u, 1]: 也是所有子树的最大值，但是由于要选u；则依据题意无法再选f(si, 1)
           所以： f[u, 1] = SUM(f[si, 0)

时间复杂度: O(n)

记忆化搜索DP(递归方式求解状态) 一般dp问题都可以写成递归的求解方式，且更容易理解
滑雪

给定一个 R 行 C 列的矩阵，表示一个矩形网格滑雪场。
矩阵中第 i 行第 j 列的点表示滑雪场的第 i 行第 j 列区域的高度。

一个人从滑雪场中的某个区域内出发，每次可以向上下左右任意一个方向滑动一个单位距离。

当然，一个人能够滑动到某相邻区域的前提是该区域的高度低于自己目前所在区域的高度。

现在给定你一个二维矩阵表示滑雪场各区域的高度，请你找出在该滑雪场中能够完成的最长滑雪轨迹，并输出其长度(可经过最大区域数)。

状态表示：
f[i, j] 集合表示所有从(i, j)开始滑的路径
属性： max

状态计算：
按照第一步向哪个方向滑分为四大类
1. 上
2. 右 (i, j) -> (i, j + 1) -> ...: 由去掉最高分小明定理即等价于给每一步去掉f(i, j)的最大值，也就是f[i, j + 1] + 1(第一步的路径长度)
    但是上述公式必须满足题意合法性：高度满足则此种情况（第一步向右）

3. 左
4. 下
易得此种分类方式不重不漏
此题递归甚至DP问题前提：必须为拓扑图（不能成环）

本题图一定不存在成环：能走说明下一步高度小于前一步，如果成环可以退出矛盾

递归求解状态一般套路：
    1. 初始化状态数组为-1(依据题意的最值)
    2. 枚举从每一个点出发的所有状态
    3. 递归处理(f[i, j]表示当前状态，dp(i, j)函数表示求出f[i, j]并返回)
    4. 递归时对于算过的状态值直接return

时间复杂度
空间复杂度
代码复杂度（好不好写）

记忆化搜索代码复杂度特别简单，方程写完既能直接写出，思路赢得太多了
运行时间稍慢，但多的话也容易爆栈。。。