For example in https://leetcode.com/problems/stickers-to-spell-word/description/
Here is a solution with memoization
class Solution(object):
def minStickers(self, stickers, target):
"""
:type stickers: List[str]
:type target: str
:rtype: int
"""
memo = {}
def is_better(target, sticker):
original_count = len(target)
for c in sticker:
target = target.replace(c, "", 1)
return target, original_count != len(target)
def dp(target, idx):
if idx >= len(stickers):
return float("inf")
if len(target) == 0:
return 0
if (idx, target) in memo:
return memo[(idx, target)]
op1 = dp(stickers, target, idx + 1)
new_target, is_use = is_better(target, stickers[idx])
op2 = float("inf")
if is_use:
op2 = dp(stickers, new_target, idx)
if op2 != float("inf"):
op2 += 1
memo[(idx, target)] = min(op1, op2)
return memo[(idx, target)]
result = dp(stickers, target, 0)
if result == float("inf"):
return -1
return result
Why is the above function have a big O of 2^T * S * T
T is the target length S is the number of characters in the sticker
Where is 2^T coming from?
My thinking is that 2^T becomes S*T after introducing memoization, and since we only iterate through the combination of number of stickers and each character in T , the big O should be # of stickers * T * O(comparing two strings)?
A similar question is https://leetcode.com/problems/target-sum/description/
class Solution(object):
def findTargetSumWays(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
memo = {}
def dp(i, sum_):
if (i, sum_) in memo:
return memo[(i, sum_)]
if i == len(nums):
if sum_ == target:
return 1
return 0
result = dp(i + 1, sum_ + nums[i]) + dp(i + 1, sum_ - nums[i])
memo[(i, sum_)] = result
return result
return dp(0, 0)
Which is O(total_sum * length of numbers) essential O(n^2) , but both problem have two branching factor in each step , and no repeating sub problems due to memoization
Why is one exponential and one quadratic? What am i missing here?