社区讨论

关于DP的疑问

学术版参与者 5已保存回复 17

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
17 条
当前快照
1 份
快照标识符
@md9jhhdk
此快照首次捕获于
2025/07/19 08:58
8 个月前
此快照最后确认于
2025/11/04 06:33
4 个月前
查看原帖
最近练了挺多DP的题,都不难,但是类别很全而且比较杂,大概包含了从背包到数位换根的一系列东西,本来是说着去CF随几道做做,结果2000左右几道题除了2个基本上都翻车了,想着调到1800好一些但是还是有个别的会卡。
所以感觉比较迷茫,似乎学了挺多但是进步微乎其微,仔细想了一下感觉是不是我DP的解题方法有问题,我大致题目看到是这么个流程:
  1. 哪种DP?
  2. 写出一个正确但是时间复杂度明显大1-2个数量级的状态
  3. 简化状态,通常是扔掉第1维(前i个)和1些套路性的优化,比如把是否可行变成可行时最小多少。
  4. 优化转移,怎么尽可能地整体转移一些看似比较重复的部分?
通常情况下第3 4步会出问题,有些时候简化完状态发现砍了不应该砍的东西转移写不出来了,或者是第4步做了个看似很正确的优化,结果写完代码对着样例调好久发现假了。
请问我上面的过程有什么地方出了问题?有没有哪些可以改进的方法?欢迎各位给我多提点建议。

回复

17 条回复,欢迎继续交流。

正在加载回复...