关于DP的疑问
  • 板块学术版
  • 楼主Epi4any
  • 当前回复17
  • 已保存回复17
  • 发布时间2025/7/11 18:30
  • 上次更新2025/7/19 08:58:24
查看原帖
关于DP的疑问
374769
Epi4any楼主2025/7/11 18:30

最近练了挺多DP的题,都不难,但是类别很全而且比较杂,大概包含了从背包到数位换根的一系列东西,本来是说着去CF随几道做做,结果2000左右几道题除了2个基本上都翻车了,想着调到1800好一些但是还是有个别的会卡。

所以感觉比较迷茫,似乎学了挺多但是进步微乎其微,仔细想了一下感觉是不是我DP的解题方法有问题,我大致题目看到是这么个流程:

  1. 哪种DP?
  2. 写出一个正确但是时间复杂度明显大1-2个数量级的状态
  3. 简化状态,通常是扔掉第1维(前i个)和1些套路性的优化,比如把是否可行变成可行时最小多少。
  4. 优化转移,怎么尽可能地整体转移一些看似比较重复的部分?

通常情况下第3 4步会出问题,有些时候简化完状态发现砍了不应该砍的东西转移写不出来了,或者是第4步做了个看似很正确的优化,结果写完代码对着样例调好久发现假了。

请问我上面的过程有什么地方出了问题?有没有哪些可以改进的方法?欢迎各位给我多提点建议。

2025/7/11 18:30
加载中...