关于DP能力提升
  • 板块学术版
  • 楼主xxseven
  • 当前回复4
  • 已保存回复4
  • 发布时间2024/9/13 09:18
  • 上次更新2024/9/13 17:06:36
查看原帖
关于DP能力提升
988025
xxseven楼主2024/9/13 09:18

这几天做了点DP,绝大部分时间都是在推状态和转移。

我发现自己设计状态的时候总是会出现缺个一维,然后死活推不出来方程,到最后迫不得已看题解才发现少了一维之类的情况。

重灾区一般是在

  • 复杂度带 O(3n)O(3^n) 子集枚举的状压
  • 数据范围小,状态数很多,复杂度 O(n4),O(n5)O(n^4),O(n^5) 这种或者在后面维度加 0/1/20/1/2 这样大常 O(n)O(n) 的树形DP

前者是怕加一维 T 了不太敢加,后者是完全想不到怎么加。

请问设计状态的能力怎么练习啊 TAT

2024/9/13 09:18
加载中...