Skip to content

DP 0-1 Knapsack

Table of Contents

2915. Length of the Longest Subsequence That Sums to Target

416. Partition Equal Subset Sum

416. Partition Equal Subset Sum - Python Solution
from functools import cache
from typing import List

from template import knapsack01


# Memoization
def canPartitionMemoization(nums: List[int]) -> bool:
    total = sum(nums)
    n = len(nums)

    if total % 2 == 1 or n <= 1:
        return False

    @cache
    def dfs(i, j):
        if i < 0:
            return j == 0
        return j >= nums[i] and dfs(i - 1, j - nums[i]) or dfs(i - 1, j)

    return dfs(n - 1, total // 2)


# DP - Knapsack 01
def canPartitionTemplate(nums: List[int]) -> bool:
    total = sum(nums)

    if total % 2 == 1 or len(nums) < 2:
        return False

    target = total // 2

    return knapsack01(nums, nums, target) == target


# DP - Knapsack 01
def canPartition(nums: List[int]) -> bool:
    total = sum(nums)

    if total % 2 == 1 or len(nums) < 2:
        return False

    target = total // 2

    dp = [0 for _ in range(target + 1)]

    for i in range(len(nums)):
        for j in range(target, nums[i] - 1, -1):
            dp[j] = max(dp[j], dp[j - nums[i]] + nums[i])

    return dp[target] == target


if __name__ == "__main__":
    nums = [1, 5, 11, 5]
    print(canPartitionTemplate(nums))  # True
    print(canPartition(nums))  # True
    print(canPartitionMemoization(nums))  # True

494. Target Sum

494. Target Sum - Python Solution
from typing import List


def findTargetSumWays(nums: List[int], target: int) -> int:

    totalSum = sum(nums)

    if abs(target) > totalSum:
        return 0
    if (target + totalSum) % 2 == 1:
        return 0

    targetSum = (target + totalSum) // 2
    dp = [0] * (targetSum + 1)
    dp[0] = 1

    for i in range(len(nums)):
        for j in range(targetSum, nums[i] - 1, -1):
            dp[j] += dp[j - nums[i]]

    return dp[targetSum]


nums = [1, 1, 1, 1, 1]
target = 3
print(findTargetSumWays(nums, target))  # 5

2787. Ways to Express an Integer as Sum of Powers

3180. Maximum Total Reward Using Operations I

474. Ones and Zeroes

474. Ones and Zeroes - Python Solution
from typing import List


def findMaxForm(strs: List[str], m: int, n: int) -> int:
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    for s in strs:
        zerosNum = s.count("0")
        onesNum = len(s) - zerosNum

        for i in range(m, zerosNum - 1, -1):
            for j in range(n, onesNum - 1, -1):
                dp[i][j] = max(dp[i][j], dp[i - zerosNum][j - onesNum] + 1)

    return dp[m][n]


strs = ["10", "0001", "111001", "1", "0"]
m = 5
n = 3
print(findMaxForm(strs, m, n))  # 4

1049. Last Stone Weight II

1049. Last Stone Weight II - Python Solution
from typing import List


def lastStoneWeightII(stones: List[int]) -> int:
    target = sum(stones) // 2

    dp = [0 for _ in range(target + 1)]

    for i in range(len(stones)):
        for j in range(target, stones[i] - 1, -1):
            dp[j] = max(dp[j], dp[j - stones[i]] + stones[i])

    result = (sum(stones) - dp[target]) - dp[target]

    return result


stones = [2, 7, 4, 1, 8, 1]
print(lastStoneWeightII(stones))  # 1

1774. Closest Dessert Cost

879. Profitable Schemes

3082. Find the Sum of the Power of All Subsequences

956. Tallest Billboard

2518. Number of Great Partitions

2742. Painting the Walls

3287. Find the Maximum Sequence Value of Array

2291. Maximum Profit From Trading Stocks

2431. Maximize Total Tastiness of Purchased Fruits

Comments