方法一：根据暴力的复杂度，以及题目所需的复杂度来判断。
方法二：归约到某一些经典问题上面。然后发现经典做法没法处理这个问题，那么说明是贪心问题。
分享一下我的做法。希望对大家有帮助。
首先这不是什么理论，只是我的一种经验，所以也不是百分百满足，但实际下来感觉还是挺有用的。这更像是一种算法直觉，所以我下面也会写得比较随意，不是很严谨。其次我这里的贪心不仅指的是贪心算法，也指一些观察，一些你需要从题目观察到有用的性质。
方法一：根据暴力的复杂度，以及题目所需的复杂度来判断。
对于dp而言，很多时候如果只依赖dp，只能够降低一个级别的复杂度。可以从阶乘级别降到指数级别，或者从指数级别降到多项式级别。比如说
- 1.从阶乘级别降低到指数级别，常见的有旅行商：。
- 2. 指数级别降到多项式级别，这个要常见的多，很多题目都是用dp从指数降到多项式的。常见的比如说背包问题：, 打家劫舍：。为什么会这样呢，有种方式理解是，我们知道dp问题实际上对应于一个DAG，而暴力做法很多时候就是在枚举这个DAG的所有路径，而在这些的图上面，路径的个数通常就是指数级别的，但是节点数是多项式级别的。
但是，如果你想一次性降低两个级别，比如说从阶乘级别直接降到多项式级别，，那就很难单纯依靠dp了。通常都是会有某些有用的贪心性质，常见的比如说按照某种方式排列，直接得到最优的排列。
总结一下就是说，如果是，那么dp是可能的。但是如果是或者更大的暴力复杂度，而题目要求，通常就是贪心（但注意这个不意味着不可能是dp，只是说不会是单纯的dp，你需要观察到一些额外的有用的性质）
方法二：归约到某一些经典问题上面。然后发现经典做法没法处理这个问题，那么说明是贪心问题。
比如说背包问题，当题目中出现说恰好等于，或者说不超过一类的字样，自然想到背包dp，但是发现数据范围很大，没法用背包问题解决时，这说明一定有什么贪心性质需要你观察到。而在lc中关于这个最最常见的，就是比如说选择k个区间，选择k个元素。因为选择k个，也可以对应于每个重量为1的背包问题，你的状态会有一个维度是给k的，状态数至少有nk的，但是你发现k很大，会超时。此时基本就是贪心了，通常就是按照某种方式从大到小选择k个，也就是这个问题具有凸性这个很好的性质。
当然不止背包问题，还有很多常见问题，比如说你知道旅行商问题是np的，但是这个问题却要求你做到，那也说明一定有贪心性质需要观察到。
不过这种方式就比较需要积累，也就是说你必须得对经典问题以及说对应的解法很熟悉。
评论 (0)
