https://leetcode.com/problems/bag-of-tokens/
一开始觉得应该是个dp 题，把所有结果搜出来然后max 一下。实现以后发现组合太多了，非常慢，即使加上memorization 也是TLE
var hash = function(arr, p, s) {
arr = arr.sort();
return arr.reduce((p, c)=>p+"-"+c, "") + "_" + p + "_" + s;
}
let m = {};
var iter = function(tokens, p, s) {
if (tokens.length == 0) return s;
let h = hash(tokens, p, s);
if (m[h] != void 0) return m[h];
let result = s;
for (let i = 0; i < tokens.length; ++i) {
//option1, if we have at leaset token[i] power
if (p >= tokens[i]) {
result = Math.max(result, iter(tokens.filter((x,k)=>k!=i), p-tokens[i], s+1));
}
//option2, if we have at least 1 point
if (s >= 1) {
result = Math.max(result, iter(tokens.filter((x,k)=>k!=i), p+tokens[i], s-1));
}
}
m[h] = Math.max(result, m[h]||0);
return result;
}
var bagOfTokensScore = function(tokens, P) {
return iter(tokens, P, 0);
};
看了答案发现是用greedy，然而也没有证明为啥greedy 就是最优解。