leetcode-dp

1049. Last Stone Weight II.py

class Solution:
    """
    we enumerate all possible combinations when cosidring all stones.
    O(2^n)
    """
    def lastStoneWeightII(self, stones: List[int]) -> int:
        """
        T: O(n*2M), where n =len(stones) and M = sum(stones). At most, we need to caclulate n*M possibilties.
        because same path will be casched.
        n comes from depth of recursion tree and M comes from at most our left_sum could be.
        S: O(n*M)
        """
        def dfs(stones, i, left_sum, right_sum, memo):
            key = (i, left_sum, right_sum)
            if key in memo:
                return memo[key]
            if i>=len(stones):
                # print (left_sum, right_sum)
                return abs(left_sum-right_sum)
            
            left = dfs(stones, i+1, left_sum+stones[i], right_sum, memo)
            right = dfs(stones, i+1, left_sum, right_sum+stones[i], memo)
            memo[key] = min(left, right)
            return memo[key]
        
        return dfs(stones, 0, 0, 0, {})