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