求教看着像数学题的DP题（比如Coin Change）

今天第一次做coin change，下意识得想用数学方法做。比如排序，然后从大到小一个个试下来。其实这种做法是错的。

之后又看到了一个题。把一个array分成2部分（无关顺序），要求这两部分的总和相等。我又去排序了。。

其实这些题暴力解+memo。

想问问大家对这些题有什么经验吗？怎么能一下想到要用暴力解。另外有类似题目也请多多举例。多看可能也就知道套路了……

DP 解法固定套路：

recursion --> recursion with memoization --> Dynamic programming
或者:
recursion --> top-down --> bottom up (Dynamic Programming)

所以DP题没思路就先递归。。

DP or 数学 都是套路。别把自己套进去了。
做题最重要的是你怎么思考这个问题。你第一眼看到题的时候应该把重心放在“咦 我该怎么分析他呢” 而不是 “咦 这是什么题？DP?”

比如这个题，第一眼不应该是这是数学还是DP？ 如果是DP 我该怎么列方程？
你应该分析：凑相等的两部分？总和是固定的，那么我一开始就能知道 我应该要凑多大的数。
现在问题变成了，一个数组，我要刚好凑到target，判断是否可能，咦这不就是背包吗。
以上才是正确的思考方式。

最开始我也是想我应该一下子看出这是什么类型的题。后来发现 太多题不能这样想。
太多题根本没有所谓的套路 考验的是你如何去分析问题，最后把问题分析到某个程度发现刚好有一个工具（二分，DP）可以去解决这个问题。这才是算法的意义。
你不能总想着一开始就拿着锤子找钉子，你得碰到钉子才用锤子。不然有时候面试官放了一个螺丝钉期盼你拿螺丝刀去拧，你一来就拿着锤子说 这钉子怎么不好锤。

自己顶一下

其实，这道题我第一做就是在数学竞赛，用的就是dp方法。。。

ymsfnm4l 发表于 2019-3-20 21:28
github.com/tianyicui/pack/blob/master/V2.pdf

确实没有意识到这个也是背包问题

coin change是什么东西啊 ，感觉能想到的就是暴力解了