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"))

Kadane's Algo:
    Maximum difference of 0's and 1's in a binary string
    Maximum Sum Circular array
    Smallest sum contiguous subarray
    Largest sum increasing contiguous subarray
    Maximum Product Subarray
    Largest sum contiguous subarray with only non-negative elements.
    Largest sum contiguous subarray with unique elements.
    Maximum Alternating Sum Subarray
    Maximum Sum Rectangle In A 2D Matrix

LIS:
    Maximum Sum Increasing Subsequence
    Print LIS
    Best Team with No Conflicts (LC 1626)
    No of LIS
    Increasing Triplet Subsequence
    LIS having sum almost K
    Minimum Number of Removals to Make Mountain Array

MCM:
    Priting MCM
    Burst Ballons
    Evaluate Expression to True/ Boolean Paranthesization
    Minimum / Maximum Value of an Expression
    Pallindrome Partitioning
    Scramble String
    Egg Dropping Problem

LCS:
    Longest Common Substring
    Print LCS
    Shortest Common Supersequence
    Print SCS
    Minimum number of insertions and deletions to from String a from String b
    Largest Repeating Subsequence
    Length of largest subsequence of which is a substring in b
    Subsequence Pattern Matching
    Count number of times a appear as subsequence in b
    Largest Pallindromic Subsequence
    Longest Pallindromic Substring
    Count of Pallindromic Substring
    Minimum deletions to make a string Pallindrome
    Minimum insertions to make a string Pallindrome
    Minimum deletions to make a->b

Unbounded Knapsack:
    Rod cutting problem
    Coin Change 1
    Coin Change 2
    Maximum Ribbon Cut
    Number Partitioning

0/1 Knapsack:
    Subset Sum
    Equal Sum Partition
    Count of subset with given sum
    Minimum subset sum difference
    Target Sum
    No of susbet with given difference
    Count of subsets with given difference
    Last Stone Weight 2(LC 1049)