开一个分享用于记录自己写过的DP题单

线性DP：

1. AcWing 313. 花店橱窗 
    Time: 2023.05.23
    描述：n类花按顺序排成一排放在m个花盆里，给出每类花在不同花盆的美观度，求美观度和的最大值。
    f[i,j]：= 第i类花只考虑放在前j个花瓶时的美观度最大值;
    状态计算: f[i,j] = max{v[i,k] + f[i-1}[k-1]}, 
              要留出i-1个花瓶放前面的花，计算好k的范围，i<=k<=j;
2. AcWing 318. 划分大理石
    Time: 2023.05.25
    描述：6种大理石价值为1-6，给出每种大理石数量，问能否分成两堆使价值相等。
    乍一看是多重背包的计数dp，用f[i][j]表示只考虑选前i类大理石作为其中一堆的所有方案中，
    价值刚好为j的方案数。但是方案数过大，会爆答案，只要有一种就可以了,用bool来存储；
    不过物品个数和价值都很大，TLE了。用二进制拆分来优化，变成01背包。
    bool f[i][j] := 只考虑选前i类大理石作为其中一堆的所有方案中，是否存在价值刚好为j的方案；
    状态计算：f[i][j] = f[i-1][j] | f[i-1][j-vi];
              f[1-6][0] = true;
3. AcWing 317. 陨石的秘密
    Time:2023.05.26
    描述：给你i对{},j对[],k对(),深度d，构造一字符串，满足[]里不能有(),{}里不能有[]和()
          求字符串深度为d的方案数。 

    f[i][j][k][d] := 由i对{},j对[],k对()构成，深度<=d的字符串的方案数;
    ans = f[i][j][k][d] - f[i][j][k][d-1];
    以左边第一个括号的类型划分集合；S = (A)B, [A]B, {A}B，3种情况的方案数累加起来。
    以[A]B为例，此时A没有{}，f[i][j][k][d] += ΣbΣc f[0][b][c][d-1]*f[i][j-b-1][k-c][d];