LeetCode Day 43 Dynamic Programming (5/17)

Its 5th Day of DP practice.

Question 1

1049. Last Stone Weight II

You are given an array of integers stones where stones[i] is the weight of the ith stone.

We are playing a game with the stones. On each turn, we choose any two stones and smash them together. Suppose the stones have weights x and y with x <= y. The result of this smash is:

• If x == y, both stones are destroyed, and
• If x != y, the stone of weight x is destroyed, and the stone of weight y has new weight y - x.

At the end of the game, there is at most one stone left.

Return the smallest possible weight of the left stone. If there are no stones left, return 0.

This problem is really about trying to get the stones to split into two piles of the same weight, with the smallest number of stones left after collision, which resolves into the 01 Knapsack problem.

The weight of the items in this problem is stones[i], and the value of the items is also stones[i]. This corresponds to the weight[i] and value[i] of the items in 01pack. The rest of the process is similar.

class Solution:
    def lastStoneWeightII(self, stones: List[int]) -> int:
        dp = [0] * 15001
        total_sum = sum(stones)
        target = total_sum // 2
 
        for stone in stones:  
            for j in range(target, stone - 1, -1):  
                dp[j] = max(dp[j], dp[j - stone] + stone)
 
        return total_sum - dp[target] - dp[target]

Question 2

494. Target Sum

You are given an integer array nums and an integer target.

You want to build an expression out of nums by adding one of the symbols '+' and '-' before each integer in nums and then concatenate all the integers.

• For example, if nums = [2, 1], you can add a '+' before 2 and a '-' before 1 and concatenate them to build the expression "+2-1".

Return the number of different expressions that you can build, which evaluates to target.

Suppose the sum of addition is x, then the corresponding sum of subtraction is sum - x.

So we require x - (sum - x) = target

x = (target + sum) / 2

At this point the Knapsack problem transforms into, how many ways to fill a knapsack of capacity x.

Here, x, is bagSize, which is the capacity of the backpack we ask for later.

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        total_sum = sum(nums)  
        if abs(target) > total_sum:
            return 0  
        if (target + total_sum) % 2 == 1:
            return 0 
        target_sum = (target + total_sum) // 2  
 
        dp = [[0] * (target_sum + 1) for _ in range(len(nums) + 1)]
 
        dp[0][0] = 1
 
        for i in range(1, len(nums) + 1):
            for j in range(target_sum + 1):
                dp[i][j] = dp[i - 1][j]  
                if j >= nums[i - 1]:
                    dp[i][j] += dp[i - 1][j - nums[i - 1]]  
 
        return dp[len(nums)][target_sum]  

Question 3

474. Ones and Zeroes

You are given an array of binary strings strs and two integers m and n.

Return the size of the largest subset of strs such that there are at most m 0’s and n 1’s in the subset.

A set x is a subset of a set y if all elements of x are also elements of y.

This question looks complicated at first glance, like a brain teaser.

The elements in the strs array in this question are the items, one for each item! And m and n are equivalent to a knapsack, in two dimensions.

class Solution:
    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
        dp = [[0] * (n + 1) for _ in range(m + 1)]  
        for s in strs:  
            zeroNum = s.count('0')  
            oneNum = len(s) - zeroNum  
            for i in range(m, zeroNum - 1, -1):  
                for j in range(n, oneNum - 1, -1):
                    dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1)  
        return dp[m][n]