dynamic_program.py

1. DP (canSum) Given a target sum and an array of positive integers,
return true if the target sum can be constructed by summing any combination of elements from the array.
You may use an element of the array as many times as needed.

#Solution
def canSum(nums, target, memo={}):
    if target in memo: return memo[target]
    if target == 0: return True
    elif target < 0: return False 
    
    for i in nums:
        if canSum(nums, target-i, memo) == True:
            memo[target] = True
            return True
        
    memo[target] = False
    return memo[target]
print(canSum([14, 7], 280))

2. DP (canConstruct) Given a target string and an array of strings (wordBank), return true if the target string can be constructed 
by concatenating elements of the wordBank.
You may reuse elements of wordBank as many times as needed

#Solution
def canConstruct(ls_strs, target, memo = {}):
    if target in memo: return memo[target] 
    if target == "": return True 
    for in_str in ls_strs:
        if in_str == target[:len(in_str)]:
            if canConstruct(ls_strs, target[len(in_str):], memo) == True:
                memo[target] = True
                return True 
                
    memo[target] = False
    return memo[target]
print(canConstruct(["m", "mm", "mmm", "mmmm", "mmmmm"], "mmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmm"))