no message

Chris Wu · Chris Wu · commit a0aaa90151df · 2021-04-19T16:27:19.000+08:00
diff --git a/problems/combination-sum-iv.py b/problems/combination-sum-iv.py
@@ -0,0 +1,24 @@
+class Solution(object):
+    def combinationSum4(self, nums, target):
+        def helper(t):
+            if t<0: return 0
+            if dp[t]>=0: return dp[t]
+            
+            ans = 0
+            for num in nums:
+                ans += helper(t-num)
+            
+            dp[t] = ans
+            return ans
+        
+        dp = [-1]*(target+1)
+        dp[0] = 1
+        
+        for i in xrange(target+1):
+            helper(i)
+        return dp[target]
+
+"""
+Time: O(TN), T is the value of target and N is the count of nums.
+Space: O(T)
+"""
diff --git a/problems/last-stone-weight-ii.py b/problems/last-stone-weight-ii.py
@@ -0,0 +1,29 @@
+"""
+dp[i][t] = considering stones[0~i-1], if it can sum up to target t
+
+Time: O(SN), S is the sum of stone weight. N is the number of stones.
+Space: O(SN), can reduce to O(S).
+"""
+class Solution(object):
+    def lastStoneWeightII(self, stones):
+        total = sum(stones)
+        target = total/2
+        dp = [[False for _ in xrange(target+1)] for _ in xrange(len(stones)+1)]
+        dp[0][0] = True
+        
+        maxSum = 0
+        # Keep trace of the max sum that stones can sum up to.
+        
+        for i in xrange(1, len(stones)+1):
+            for t in xrange(target+1):
+                if (dp[i-1][t] or (t-stones[i-1]>=0 and dp[i-1][t-stones[i-1]])):
+                    # it can sum up to t considering stones[0~i-2]
+                    # OR
+                    # it can sum up to t considering stones[0~i-1]
+                    dp[i][t] = True
+                    maxSum = max(maxSum, t)
+                    if t==target: return total-maxSum*2
+        
+        # Two collection of stones will be total-maxSum and maxSum
+        # (total-maxSum) - maxSum => total-maxSum*2
+        return total-maxSum*2
diff --git a/problems/last-stone-weight.py b/problems/last-stone-weight.py
@@ -0,0 +1,26 @@
+import bisect
+class Solution(object):
+    def lastStoneWeight(self, stones):
+        stones.sort()
+        
+        while len(stones)>1:
+            x = stones.pop()
+            y = stones.pop()
+            bisect.insort_left(stones, abs(x-y))
+
+        return 0 if not stones else stones[0]
+
+import heapq
+class Solution(object):
+    def lastStoneWeight(self, stones):
+        h = []
+        
+        for stone in stones:
+            heapq.heappush(h, stone*-1)
+        
+        while len(h)>1:
+            x = heapq.heappop(h)
+            y = heapq.heappop(h)
+            heapq.heappush(h, abs(x-y)*-1)
+        
+        return 0 if not h else abs(h[0])
diff --git a/problems/partition-array-for-maximum-sum.py b/problems/partition-array-for-maximum-sum.py
@@ -0,0 +1,14 @@
+"""
+dp[i] = maxSumAfterPartitioning(A[0~i-1], K) and must contain A[i-1]
+"""
+class Solution(object):
+    def maxSumAfterPartitioning(self, A, K):
+        dp = [0 for _ in xrange(len(A)+1)]
+
+        for i in xrange(1, len(A)+1):
+            m = float('-inf') # max in A[i-k]~A[i-1]
+            for k in xrange(1, min(i+1, K+1)):
+                m = max(m, A[i-k])
+                dp[i] = max(dp[i], m*k + dp[i-k])
+
+        return dp[-1]
diff --git a/problems/target-sum.py b/problems/target-sum.py
@@ -0,0 +1,31 @@
+class Solution(object):
+    def findTargetSumWays(self, nums, S):
+        stack = [(0, 0)]
+        ans = 0
+        
+        while stack:
+            i, s = stack.pop()
+            if i==len(nums) and s==S: ans += 1
+            if i>=len(nums): continue
+            
+            stack.append((i+1, s+nums[i]))
+            stack.append((i+1, s-nums[i]))
+        
+        return ans
+
+import collections
+
+
+
+class Solution(object):
+    def findTargetSumWays(self, nums, target):
+        S = sum(nums)
+        dp = [collections.Counter() for _ in xrange(len(nums)+1)]
+        dp[0][0] = 1
+        
+        for i in xrange(1, len(nums)+1):
+            for j in xrange(-S, S+1):
+                dp[i][j] = dp[i-1][j+nums[i-1]] + dp[i-1][j-nums[i-1]]
+        
+        return dp[len(nums)][target]
+        
