[LeetCode]Take Coins

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

	class Solution {
	public:
	/**
	* @param list: The coins
	* @param k: The k
	* @return: The answer
	*/
	int takeCoins(vector<int> &list, int k) {
	// Write your code here
	vector<int> preSums;
	int sum = 0, len = list.size();
	//left to right
	for(int i = 0; i < k; ++i)
	{
	sum += list[i];
	preSums.push_back(sum);
	}
	//right to left
	sum = 0;
	int res = preSums[k - 1];
	for(int i = 1; i <= k; ++i)
	{
	sum += list[len - i];
	int currSum = sum + preSums[k - i - 1];
	res = max(currSum, res);
	}
	return res;
	}
	};

view raw Take Coins.cpp hosted with ❤ by GitHub