[LeetCode]Take Coins

Brute Force的做法DFS，每次取左边或者右边，遍历所有的可能，时间复杂度O(2^k)，k为取硬币的次数。但事实上，如果我们左边取了x个，右边只能取k - x个。那么我们只需要遍历某一边对应取了0到k个的情况，那么另外一边也可以由此确定。首先计算出左边到k个为止的presum，然后右边一次枚举0到k即可。时间复杂度O(k)，代码如下：