Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
leetcode-dp
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, {})
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment