-
Notifications
You must be signed in to change notification settings - Fork 0
/
stoneGameIII.js
45 lines (40 loc) · 1005 Bytes
/
stoneGameIII.js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
const helper = (stones, i, dp) => {
if (dp[i]) return dp[i];
if (i >= stones.length) {
dp[i] = 0;
return 0;
}
let answer = Number.MIN_SAFE_INTEGER;
// Pick 1 stone
answer = Math.max(answer, stones[i] - helper(stones, i + 1, dp));
// Pick 2 stone
if (i + 1 < stones.length)
answer = Math.max(
answer,
stones[i] + stones[i + 1] - helper(stones, i + 2, dp)
);
// Pick 3 stone
if (i + 2 < stones.length)
answer = Math.max(
answer,
stones[i] + stones[i + 1] + stones[i + 2] - helper(stones, i + 3, dp)
);
dp[i] = answer;
return answer;
};
/**
* @param {number[]} stoneValue
* @return {string}
*/
var stoneGameIII = function (stoneValue) {
const dp = {};
const alice = helper(stoneValue, 0, dp);
if (alice > 0) return "Alice";
else if (alice === 0) return "Tie";
return "Bob";
};
const test = () => {
console.log(stoneGameIII([1, 2, 3, 7]) === "Bob");
console.log(stoneGameIII([1, 2, 3, -9]) === "Alice");
};
test();