Analysis is more important than code

If you are preparing interviews from top tech company, one advice is problem analysis is more important than code. Here is an example.

877. Stone Game

DP works, however, the complexity is kind of O(2^n), so we will get TLE.

from functools import lru_cache
class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        half = sum(piles)//2
        @lru_cache(None)
        def dp(i,j,cur_a, cur_b):
            if cur_a > half:return True
            if i==j:
                if cur_a+piles[i]<cur_b:return False
                return True
            else:
                casea, caseb =dp(i+1, j, cur_b,cur_a+piles[i]), dp(i, j-1, cur_b,cur_a+piles[j])
                if casea and caseb:return False
                else:return True
        return dp(0, len(piles)-1, 0, 0)

Further analysis can be found here and the code is only one line:

return True

https://leetcode.com/problems/stone-game/discuss/154610/DP-or-Just-return-true