alues[i] + values[i + 1] + min(P[i + 3], P[i + 4])) P[i % 5] = max(values[i] + min(b, c), values[i] + a + min(c, d)); } return P[0] > sum - P[0]; } }; // Time: O(n) // Space: O(n) class Solution2 { public: /** * @param values: a vector of integers * @return: a boolean which equals to true if the first player will win */ bool firstWillWin(vector &values) { vector P(values.size()); int sum = 0; for (int i = values.size() - 1; i >= 0; --i) { sum += values[i]; const int a = i + 1 < values.size() ? values[i + 1]: 0; const int b = i + 2 < values.size() ? P[i + 2] : 0; const int c = i + 3 < values.size() ? P[i + 3] : 0; const int d = i + 4 < values.size() ? P[i + 4] : 0; // P[i] = max(values[i] + min(P[i + 2], P[i + 3]), // values[i] + values[i + 1] + min(P[i + 3], P[i + 4])) P[i] = max(values[i] + min(b, c), values[i] + a + min(c, d)); } return P[0] > sum - P[0]; } }; 4:["$","div",null,{"children":[["$","header",null,{"children":[["$","div",null,{"className":"text-3xl text-bold p-0 mt-2 mb-2","children":["$","h1",null,{"children":["Coins in a Line II",["$","span",null,{"className":"font-mono text-sm text-gray-500","children":"(LintCode 395):"}]]}]}],""]}],["$","article",null,{"children":[["$","div",null,{"className":"p-0","dangerouslySetInnerHTML":{"__html":"

Problem description: Visit and Support LintCode Search via
Difficulty: Medium
Tags:

Problem