跳转至

DP问题：

  • 背包问题
  • 线性DP
  • 区间DP
  • 计数类DP
  • 数位统计DP
  • 状态压缩DP
  • 树形DP
  • 记忆化搜索

通用DP思维

  • 状态表示

    • 集合：

      • 所有只从前i个物品选取，总体积<=j的宣发
        • 属性：Max，Min，数量
      • 状态计算：
        • 集合划分：做到不重不漏
      • 不选的情况：没选的前0~n个，以及容量为0时的所有情况。
      • 含i：f(i-1,j)
      • 不含i:f(1i,j-v1)+v2，从1i中选，总体积至少要保证当前v1加上够用。
        • 根据属性，对含i和不含i的结果进行综合

滚动数组

每次都只根据当前层和上一层来算，那么这种二维DP就可以优化成滚动数组：即把上一次的结果当做上一层拿来重新计算当前层

01背包

推导：f[i,j] = MAx(f[i-1,j], f[i-1,j-v[i]] + w[i]) 每种只拿一个，那么只能完全根据上一层结果算，不能利用当前计算过后的结果再次计算。 滚动数组优化：由于计算需要拿前面的计算结果，所以新的计算先算出后面的结果再往前算，可以保证前面的历史结果不被覆盖。

完全背包

1.暴力做法

本质上是f[i,j] = f[i - 1, j - v[i] * k] + w[i] * k,（v是大小，w是价值），k理论上可以取无限大，只要小于背包大小。 但这样时间复杂度过高，因为要判断范围内所有的可选k值的结果，ijk三重循环。

2. 优化做法（常规做法）：

f[i,j]和f[i,j-v]推导式可能差一个v[i] * (k-(k-1)) == v[i]. 因此，咱们优化的方式，即利用之前计算过的n个k的结果。

推导：f[i,j] = MAx(f[i-1,j], f[i,j-v[i]] + w[i])

可以看到只与01背包有个i和i-1的区别。01只拿上一层，而完全需要利用当前层计算的结果。

每种可以拿无数个，根据上一层结果和当前已计算的结果继续叠加，可以利用当前计算过后的结果再次计算。

3. 滚动数组优化

滚动数组优化：正序计算，利用到算出的结果

多重背包

需要滑动窗口最大值的思想，可以用单调队列。

1.暴力做法

本质上是f[i,j] = f[i - 1, j - v[i] * k] + w[i] * k,（v是大小，w是价值） 推导方程其实和完全背包一样，不过k不是根据背包算，除了完全背包的小于背包大小。还有自己的数量限制。

2. 完全背包的优化方式是否可行？

请看，若一个背包大小顶多装下s个v Pasted image 20250823150345

f[i,j]不能利用前面算出来的值（因为数量有限，前面可能已经把数量用光了）

3. 01背包拆解

可以把容量为s的背包暴力的全部拆成s个01背包，时间复杂度n v s

4. 二进制优化拆解01背包

2000可以拆成1,2,4,8·····等多个背包，时间复杂度直接变为n v log2S。

int cnt = 0;
for(int i = 1;i <= n;i ++)
{
    int a,b,s;
    ...
    int k = 1;

    //二进制分组
    while(k <= s)
    {
        cnt ++;
        v[cnt] = a * k;
        w[cnt] = b * k;
        s -= k;
        k *= 2;
    }

    //剩余的再分一组
    if( s > 0 )
    {
        cnt ++;
        v[cnt] = a * s;
        v[cnt] = b * s;
    }
}

分组背包问题

每一组只能选一个，但是每一个物品的大小和价值也都不一样。

dp公式：f[i-1, j - v[i,k]] + w[i,k]

滚动优化