DP Knapsack

Lot of DP problems has some similarity to 0–1 Knapsack problem.

The naive 0–1 Knapsack problem has the complexity of O(2^n) as for each item we have two options. The improved one has the complexity of O(NW)

Solution of 0–1 Knapsack problem with O(NW) complexity can be found on the following slides p35.

https://www.cs.princeton.edu/~wayne/kleinberg-tardos/pdf/06DynamicProgrammingI.pdf

We have some similar DP problems for which the complexity by using naive DP is O(2^n) and it is required to be improved to a more efficient DP algorithm. I will give several examples.

871. Minimum Number of Refueling Stops

Naive DFS essencially same to naive DP has the complexity of O(2^N) and got TLE as expected.

class Solution:
    def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:
        if not stations:
            if target>startFuel:return -1
            else: return 0
        stations.append([target, 0])
        def dfs():
            res = float('inf')
            open_list = [(0, startFuel, 0, 0)]
            while open_list:
                i, f, d,dis = open_list.pop()
                if dis==target:
                    if d<res:
                        res = d
                    continue
                gas_used = stations[i][0] - (0 if i==0 else stations[i-1][0])
                fuel = stations[i][1]
                if f-gas_used>=0:
                    if d+1<res:
                        open_list.append((i+1, f-gas_used+fuel, d+1, stations[i][0]))
                    if d<res:
                        open_list.append((i+1, f-gas_used, d, stations[i][0]))
            return -1 if res==float('inf') else res
        return dfs()

Improved DP rocks with complexity of O(N²). Solution is borrowed from lee215. Original link is here:

DP O(N^2) and Priority Queue O(NlogN) - LeetCode Discuss

DP solution O(n²) 1380ms

class Solution:
    def minRefuelStops(self, target: int, startFuel: int, s: List[List[int]]) -> int:
        dp = [startFuel] + [0] * len(s)
        for i in range(len(s)):
            for t in range(i + 1)[::-1]:
                if dp[t] >= s[i][0]:
                    dp[t + 1] = max(dp[t + 1], dp[t] + s[i][1])
        for t, d in enumerate(dp):
            if d >= target: return t
        return -1

DP solution with priority queue O(nlogn) 120 ms

import heapq
class Solution:
    def minRefuelStops(self, target: int, cur: int, s: List[List[int]]) -> int:
        pq = []
        res = i = 0
        while cur < target:
            while i < len(s) and s[i][0] <= cur:
                heapq.heappush(pq, -s[i][1])
                i += 1
            if not pq: return -1
            cur += -heapq.heappop(pq)
            res += 1
        return res

879. Profitable Schemes

“Well, it is a Knapsack problem and my first intuition is dp.

dp[i][j] means the count of schemes with i profit and j members.

The dp equation is simple here:
dp[i + p][j + g] += dp[i][j]) if i + p < P
dp[P][j + g] += dp[i][j]) if i + p >= P

Don’t forget to take care of overflow.

For each pair (p, g) of (profit, group), I update the count in dp.

Time Complexity:
O(NPG)

”

class Solution:
    def profitableSchemes(self, G: int, P: int, group: List[int], profit: List[int]) -> int:
        # dp[g][p]
        dp = [[0]*(G+1) for i in range(P+1)]
        dp[0][0] = 1
        for g, p in zip(group, profit):
            for i in range(P, -1, -1):
                for j in range(G-g, -1, -1):
                    dp[min(P, i+p)][j+g] += dp[i][j] 
        return sum(dp[P])%(10**9+7)