<jupyter_start><jupyter_text>Dynamic Programming Solutions to Well-Known Problems: Longest Common Substring,  Longest Common Subsequence, Min Coin Change Problem, All Ways to Reach a Target, Knapsack Value Optimization, Longest Increasing Subsequence, Longest Common Increasing Subsequence, Edit Distance (The Levenshtein Distance) Problem, Matrix Rotation Operations, Minimum Number of Scalar Multiplications for Chain Multiplication of Matrices, Partition Problem, Max Profit on Rod Cutting Problem, Word Break (Segmentation) Problem<jupyter_code># Dynamic Programming Solution to longest common substring of two strings problem

import numpy as np
X = 'qalkfaoik'
Y = 'qfaoianok'

def LCsubstring(x, y):
    n = len(x)
    m = len(y)
    # create a 2D known list to store the sub-solutions
    known_list = np.zeros([n+1, m+1], dtype = int)
    # create a list to return the solution
    lcs = []
    # set a variable to find the maximum length
    longest = 0
    # loop over the rows 
    for i in range(1, n+1):
        # loop over the columns
        for j in range(1, m+1):
            # if there is a match, move down one step diagonally on the matrix and increase the value by one
            if x[i-1] == y[j-1]:
                known_list[i][j] = known_list[i-1][j-1] + 1
                c = known_list[i][j]
                if c > longest: # if it is the longest substring
                    longest = c
                    lcs = []
                    lcs.append(x[i-longest: i])

    print(known_list)
    return lcs            
            
LCsubstring(X,Y)              

# Solution to finding the longest substring of a string with at most 2 distinct characters
# Samples: input: 'ababcbcbaaabbdef', result : ['baaabb']

def lsubstr_with_2_char(string):
    substring = []
    longest = 0
    for i in range(len(string)):
        c_set = set()
        for j in range(i,len(string)):
            c_set.add(string[j])
            if len(c_set) > 2:
                break
            if j-i > longest:
                longest = j-i
                substring = []
                substring.append(string[i:j+1])
            elif j-i == longest: # if there is more than one with the same length
                substring.append(string[i:j+1])
    return substring

s = 'ababcbcbaaabbdef'
print(lsubstr_with_2_char(s))


# Another solution to finding the longest substring of a string with at most 2 distinct characters, another solution
s = 'ababcbcbaaabbdef'

def lsubstr_with_2_char2(string):
    longest = 0
    for i in range(len(string)):
        substring = []
        c_set = set()
        for j in range(i,len(string)):
            c_set.add(string[j])
            if len(c_set) > 2:
                break
            substring.append(string[j])
            if len(substring) > longest:
                longest = len(substring)
                longest_substring = substring
                
    return "".join(longest_substring)

s = 'ababcbcbaaabbdef'
print(lsubstr_with_2_char2(s))
# Dynamic programming solution to longest common subsequence of two strings problem

X = 'thisisatest'
Y = 'testing123testing'

import numpy as np
def LCSub(x, y):
    # create a known list to store the subproblems and build it bottom up
    n = len(x)
    m = len(y)
    known_list = np.zeros([(n+1),(m+1)], dtype = int) # it is a 2d array with n+1 # of rows and m+1 # of columns
    # loop over rows
    for i in range(1, n+1):
        # loop over columns
        for j in range(1, m+1):
            # if there is a match increase the value of that cell diagonally by one
            if x[i-1] == y[j-1]:
                known_list[i][j] = known_list[i-1][j-1] + 1
            # if there is no match then take either the previous item on string x or string y 
            else:
                known_list[i][j] = max(known_list[i][j-1], known_list[i-1][j])
    print(known_list)
    # after building the known list loop over the inputs again and follow the path from bottom right to top left
    i = n
    j = m
    lcs_list = []
    while 0 < i and 0 < j:
        if x[i-1] == y[j-1]:
            lcs_list.insert(0, x[i-1])
            i -= 1
            j -= 1
        elif known_list[i-1][j] > known_list[i][j-1]:
            i -= 1
        else:
            j -= 1
    return lcs_list

LCSub(X,Y)  




# Dynamic programming solution to min coins needed for a change using one array
# Use one array to store the sub solutions

def min_coin_change1(coinValueList,change):
    known_results = [0] * (change+1)
    for cents in range(1, len(known_results)):
        coinCount = cents
        for j in [c for c in coinValueList if c <= cents]:
            num_coins = known_results[cents-j] + 1
            if num_coins < coinCount:
                coinCount = num_coins
        known_results[cents] = coinCount
    print(known_results)
    return known_results[change] 

change_list = [1,3,5,10]
target = 21
print(min_coin_change1(change_list, target))
# Dynamic programming solution to min coins needed for a change (even more simplified)
# Use one array to store the sub solutions

def min_coin_change2(coinValueList,change):
    known_results = np.arange(0, change + 1, dtype = int) # start with the worst case scenerio, just pay with 1 cent
    for cents in range(1, len(known_results)):
        for j in [c for c in coinValueList if c <= cents]:
            known_results[cents] = min(known_results[cents - j] + 1, known_results[cents])
    print(known_results)
    return known_results[change] 

change_list = [1,3,5,10]
target = 21
print(min_coin_change2(change_list, target))
# Dynamic programming solution to min coins needed for a change using a matrix
# using a matrix to store the values

change = [1,3,5,10]
target = 21

def minimum_coin_change3(coins, total):
    n = len(coins)
    memo_list = np.zeros([n+1, total + 1], dtype = int)
    for j in range(1, total + 1):
        memo_list[0][j] = j # if one penny is used, each cell would be equal to the target value paid fully by pennies
    for i in range(1, n+1):
        for j in range(1, total+1):
            coin_value = coins[i-1]
            if coin_value <= j: # consider all coins smaller than the target               
                memo_list[i][j] = min(memo_list[i-1][j], memo_list[i][j-coin_value]+1)
            else:
                memo_list[i][j] = memo_list[i-1][j]
           
    print(memo_list)
    return memo_list[n][total]
minimum_coin_change3(change, target)
# Dynamic programming solution to min coins needed for a change needed problem using a matrix to store the values
# Alternative solution to the one above 

change = [1,3,5,10]
target = 21

def minimum_coin_change4(coins, total):
    n = len(coins)
    memo = np.zeros([n+1, total + 1], dtype = int)
    for j in range(1, total + 1):
        memo[0][j] = j
    # print(dp)
    for i in range(1, n+1):
        for j in range(1, total+1):
            coin_value = coins[i-1]
            if coin_value > j: # if coin value is bigger than the current target capacity, don't include this coin
                memo[i][j] = memo[i-1][j] 
            else:
                memo[i][j] = min(memo[i-1][j], memo[i][j-coin_value]+1)
           
    print(memo)
    return memo[n][total]
minimum_coin_change4(change, target)

# Reminder: Recursive solution to reach a target in all possible ways with given list of steps

def reach_t(list_of_numbers, target, result = None, sub_solution = None):
    if result == None: result = []
    if sub_solution == None: sub_solution = []
    if sum(sub_solution) > target: return
    if sum(sub_solution) == target: result.append(sub_solution)
    # loop over all the items in the list
    for i in range(len(list_of_numbers)):
        reach_t(list_of_numbers, target, result, sub_solution + [list_of_numbers[i]])
    return result

solution = reach_t([1,2,3], 4)
print(solution)
%timeit reach_t([1,2,3], 4)

# print the min number of steps to reach the target:
print(min([len(solution[i]) for i in range(len(solution))]))  # takes minimum 2 steps to reach target
# Reminder: Recursive solution to print breakdown of all combinations of the elements of a list

def reach_t(list_of_numbers, result = None, sub_solution = None):
    if result == None: result = []
    if sub_solution == None: sub_solution = []
    result.append(sub_solution)
    # loop over all the items in the list
    for i in range(len(list_of_numbers)):
        remainder = list_of_numbers[:i] + list_of_numbers[i+1:] 
        reach_t(remainder, result, sub_solution.append(list_of_numbers[i]))
    result = [n for i, n in enumerate(result) if n not in result[:i]] # erase all the duplicate items in the list
    return result

solutions = reach_t([1,2,3])
print(solutions)
# Dynamic programming solution to find all possible steps to cover a distance problem 
# Reach a target by using a list of all integers that are all smaller than or equal to the target

steps = [1,2,3]
target = 4

def count_ways_to_reach_target(target, step_list): 
    res = [0 for x in range(target+1)] # Creates list res with all elements 0 
    res[0] = 1 
    for i in range(1, target+1): 
        for j in [c for c in step_list if c <= target]:
            res[i] += res[i-j]
    print(res)
    return res[target]
count_ways_to_reach_target(target,steps) 
      
# Dynamic programming solution to the knapsack problem

import numpy as np
def knapsack(weight_list, value_list, weight_capacity):
    n = len(value_list)
    # create a 2 dimensional array, a table, to store the solved sub-problems, zero pad the index 0 and column 0
    known_list = np.zeros([n+1, weight_capacity+1], dtype = int) 
    # each value in the matrix will represent the best value that can be reached at present weight capacity
    # loop over each item (indices will be the rows and weight capacity is in columns)
    for item in range(1, n+1):
        # loop over each weight
        for curr_w_capacity in range(1, weight_capacity+1):
            # if there is better value for particular weight than what is already seen, replace the value
            current_item_weight = weight_list[item-1] 
            current_item_value = value_list[item-1]
            value_at_curr_capacity = known_list[item-1][curr_w_capacity]
            if current_item_weight <= curr_w_capacity: # then consider putting the item in the sack
                previous_weight = curr_w_capacity - current_item_weight
                previous_value_of_sack = known_list[item-1][previous_weight]
                known_list[item][curr_w_capacity] = max((current_item_value + previous_value_of_sack), value_at_curr_capacity)
            else:
                known_list[item][curr_w_capacity] = value_at_curr_capacity
    print(known_list)
    # return the known_list with the max weight_capacity for max value
    return known_list[n][weight_capacity]   
   
if __name__ == "__main__": 
    print(knapsack([3,5,4], [8,2,7], 10))
# Solution to find the length of the longest increasing subsequence problem 

import numpy as np
def LIS(numbers):  # with two for loops, simple Longest Increasing Subsequence
    n = len(numbers)
    ranking = [1 for i in range(n)] # ranking is set to 1, if there is no sequence, it will be just one number
    for i in range(n):  # all the numbers
        for j in range(i+1, len(numbers)):
            # check if the remaining items have lower rank but higher value and re-adjust the ranking
            if numbers[i] < numbers[j] and ranking[i] >= ranking[j]:
                ranking[j] = ranking[i] + 1
                
    return max(ranking) , ranking
   
if __name__ == '__main__':
    print(LIS([5, 3, 8, 2, 4, 6, 1, 4, 5, 3]))
  
# Solution to find the elements of the longest increasing subsequence problem. 
# ATTN: There might always be several longest increasing subsequences with same length 
# ex: [4, 5, 0, 1, 8, 2, 10]  answer: 4,5,8,10 and 0,1,2,10
# Print the elements of one of the longest increasing subsequences 

test_array = [4, 0, 1, 8, 2, 10]

def Print_LISubsequence(a):
    # create a ranking array and a parent array
    ranking = np.ones(len(a), dtype = int) # dtype is very important!
    # loop over the array
    for i in range(len(a)):
        # loop over all the remaining items ahead of the current item
        for j in range(i+1, len(a)):
            # check if the remaining items have lower rank but higher value
            # if this is the case, increase the rank of the further items and assign them as parent
            if a[i] < a[j] and ranking[i] >= ranking[j]:
                ranking[j] = ranking[i] + 1
    print(ranking)
    max_rank_at = int(max(ranking))
    order_list = []
    for each_rank in reversed(range(len(ranking))):
        if ranking[each_rank] == max_rank_at:
            order_list.insert(0, a[each_rank])
            max_rank_at -= 1
    return order_list      
    
Print_LISubsequence(test_array)
# Solution to finding the length of the longest common increasing subsequence (LCIS) 
import numpy as np

arr1 = [4, 0, 8, 2, 10] # LCS: 4,8,2,10 & LCIS: 4, 8, 10 & LCIS should be: [0,1,2,1,3]
arr2 = [3, 4, 8, 2, 10] 
# create the ranking array with the same length of arr2 

def LCIS(arr1, arr2): 
    n = len(arr1)
    m = len(arr2)
    lcis_ranking_array = np.zeros(m, dtype = int) # for all indices store how many of lci element is seen so far
    # Loop over the first array
    for i in range(n): 
        # Initialize current max length
        max_number_of_lci_elements_seen = 0
        # For each element of arr1[], traverse all elements of arr2[]. 
        for j in range(m):
            # if there is a match and the array is not updated, update the array
            if (arr1[i] == arr2[j]): 
                max_number_of_lci_elements_seen += 1
                lcis_ranking_array[j] = max_number_of_lci_elements_seen 
            
            # if the compared element in arr2[j] is smaller but it had been building another branch of lcis within 
            # do not change the lcis ranking values but reset the length of the maximum number of lcis 
            elif (arr1[i] > arr2[j]) and lcis_ranking_array[j] > max_number_of_lci_elements_seen:
                max_number_of_lci_elements_seen = lcis_ranking_array[j]
            
    print(lcis_ranking_array) # view the ranking array 
    return max(lcis_ranking_array)

LCIS(arr1, arr2)
# Solution for printing the longest common increasing subsequence elements of two arrays

arr1 = [4, 0, 8, 2, 10] # LCS: 4,8,2,10 & LCIS: 4, 8, 10 & LCIS should be: [0,1,2,1,3]
arr2 = [3, 4, 8, 2, 10]   

# answer is 4,8,10

def Print_LCIS(arr1, arr2): 
    
    n = len(arr1) 
    m = len(arr2)
    # create ranking and parent arrays 
    ranking = [0 for i in range(m)] 
    parent = [0 for i in range(m)] 
    # loop over all elements in the first array
    for i in range(n): 
        min_ranking = 0
        parent_index = -1
        # loop over all elements in the second array
        for j in range(m): 
            if arr1[i] == arr2[j] and min_ranking >= ranking[j]: 
                # if the item is common and its ranking is small, increase its rank, update parent value
                ranking[j] = min_ranking + 1
                parent[j] = parent_index     
           
            if arr1[i] > arr2[j] and ranking[j] > min_ranking: 
                # if any item is smaller and its ranking is large, set the new rank value, set new parent index value
                min_ranking = ranking[j] 
                parent_index = j 
    
    # The ranking and parent arrays are completed. Ranking array will only be useful to decide where to begin to 
    # start appending LCIS list as it has the max ranking value at some of its indices. 
    
    # The maximum value in ranking 
    result = max(ranking)
    
    # find the index of the max ranking value (shortest version is: index_at_max = np.argmax(ranking))
    for i in range(len(ranking)):
        if ranking[i] == result:
            index_at_max = i

    # LCIS is going to store elements of LCIS, follow the parent array
    lcis = []
    while(index_at_max != -1): 
        lcis.insert(0, arr2[index_at_max])
        index_at_max = parent[index_at_max] 
  
    print(lcis, parent, ranking, arr1, arr2) # to view the ranking and parent arrays
    
    return lcis
  

Print_LCIS(arr1, arr2)
# Dynamic Programming solution to the Levenshtein Distance (commonly known as "Edit Distance") problem
# Find minimum number of edits (operations) required to convert ‘str1’ into ‘str2’. Time complexity is: O(mxn). 

import numpy as np

def edit_distance(str1, str2): 
    m = len(str1)
    n = len(str2)
    known_list = np.zeros([(m+1),(n+1)], dtype = int)
    # Traverse the first string
    for i in range(m+1): 
        # Traverse the second string
        for j in range(n+1): 
            # If first string is empty, insert all characters of second string
            if i == 0: 
                known_list[i][j] = j    
            # If second string is empty, remove all characters of second string 
            elif j == 0: 
                known_list[i][j] = i    # Min. operations = i 

            # If characters are same, do nothing but move forward
            elif str1[i-1] == str2[j-1]: 
                known_list[i][j] = known_list[i-1][j-1] 
  
            # If last character are different, consider all possibilities and find the minimum until this point
            else: 
                known_list[i][j] = 1 + min(known_list[i][j-1], known_list[i-1][j], known_list[i-1][j-1])    
    
    print(known_list) # to view all results       
    return known_list[m][n]
  
# Test set
str1 = "sunday"
str2 = "saturday" 
# Answer: 3
  
print(edit_distance(str1, str2)) 
# Dynamic Programming to obtain the minimum number of scalar multiplications needed to compute the matrix A[i..j] 
# Each matrix Ai has dimensions p[i-1] x p[i] for i = 1..n 
# There are 4 matrices of dimensions 5x4, 4x6, 6x2 and 2x7 in the below example

arr = [4, 2, 3, 1, 2]
import numpy as np
def MatrixChainOrder(p): # where dimension of A[i] is p[i-1] x p[i].
    n = len(p)
    m = np.zeros([n, n])
    # m[i,j] = Minimum number of scalar multiplications needed to compute the matrix A[i]A[i+1]...A[j] = A[i..j]  
    # L is chain length. L = 1 will have m[i][j] = 0 since the matrix can't be multiplied by itself.
    for L in range(2, n):  
        for i in range(1, n-L+1): # for L in range 2,3,4 and n being 5, the i gets range is: 1,4 1,3 1,2
            j = i+L-1 # move the i,j diagonally from top left to bottom right
            m[i][j] = np.inf # set a value to optimize which i,j has the best value for k within [i to j]
            for k in range(i, j): 
                q = m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j] # q = cost of scalar multiplications 
                if q < m[i][j]: 
                    m[i][j] = q 
                print(i, j, k, m[i][j]) # view all multiplications performed
  
    print(m) # view all optimizations made, think of the table as a tree, move the table counter clockwise 45 degrees
    return m[1][n-1] # return the value for the min scalar multiplication (the top value of the tree)
MatrixChainOrder(arr)
# GREEDY approach of matrix chain multiplication order, definetely DOES NOT guarantees the best solution! 
# This approach only picks the two Mi[a,b]*Mj[b,a] at a time for min multiplications 
# in other words, the below code just picks the best first multiplication at a time of an array of matrices
# There are 4 matrices of dimensions 5x4, 4x6, 6x2 and 2x7 in the below example

arr = [5, 4, 6, 2, 7]
# Take any 3 numbers in a row, multiply them and eliminate the middle one. 
# Find the total min number until only 2 numbers are left.

def matrix_multiplication(matrices_array, total_multiplications = None):
    n = len(matrices_array)
    if n < 3: return
    if total_multiplications == None: total_multiplications = []
    # memo = np.zeros([n, n], dtype = int)
    min_q = np.inf
    # calculate the cheapest multiplication among all matrices in order
    for i in range(0, n-2): 
        q = matrices_array[i] * matrices_array[i+1] * matrices_array[i+2]
        if min_q > q:
            min_q = q
            mark_index = i+1
    # eliminate the middle matrix and form a new array
    resulting_array = [matrices_array[i] for i in range(len(matrices_array)) if i != mark_index]
    # store the multiplications performed
    total_multiplications.append(min_q)
    # continue until only 1 matrix (an array with length 2) is left
    matrix_multiplication(resulting_array, total_multiplications)
    print('\n')
    print('multiplications made for this merge:', min_q)
    print('remaining matrix array:', resulting_array)
    print('matrices array where 2 of the matrices will merge:', matrices_array)
    # matrix_multiplication(resulting_array)         
    return sum(total_multiplications)

matrix_multiplication(arr)

# Dynamic programming solution for equal sum sub-sets partition problem with time complexity: O(n*k)
# Same algorithm with finding if any combination of sum of some elements in a list is equal to the target. 

arr1 = [5,4,1,2]
import numpy as np  

def print_two_equal_sum_sets(arr): 
    n = len(arr)
    if sum(arr) % 2 == 1: return False # if sum / 2 is odd the array can't be partitioned to two equal subsets 
    k = sum(arr) // 2  # the sum of both subsets will be k 
    # dp[i][j] = 1 if there is a subset of elements in first i elements of array that has sum equal to j.  
    memo_table = np.zeros((n + 1, k + 1))   
    for i in range(n + 1):  # TRUE if the array has 0 elements
        memo_table[i][0] = 1
    # check if the any combination of elements until index i, is equal to curr_sum 
    for i in range(1, n + 1): # traverse each element
        for currSum in range(1, k + 1):  # for each sum subset value
            if arr[i-1] <= currSum: # if current item can fit to the sum
                memo_table[i][currSum] = memo_table[i-1][currSum] or memo_table[i-1][currSum - arr[i-1]]
            else:
                memo_table[i][currSum] = memo_table[i-1][currSum]
    
    # If the answer needed was a TRUE or FALSE, we could just return the dp[n][k] value
    print(memo_table) # view the memo table 
    
    # If partition is not possible, return False 
    if memo_table[n][k] == 0: return False
    
    # partition part requires creating two sets and separating the items list 
    set1, set2 = [], [] 

    # Start from last element and percolate up
    i = n  
    currSum = k  
    while (i > 0 and currSum >= 0) : 
        if (memo_table[i - 1][currSum]): 
            set1.append(arr[i-1]) 
            print('item: {} goes to set 1, see indices {} and {} is 1'.format(arr[i-1], i-1, currSum))  
        elif (memo_table[i - 1][currSum - arr[i - 1]]): 
            print('item: {} goes to set 2, see indices {} and {} is 0'.format(arr[i-1], i-1, currSum))
            set2.append(arr[i-1]) 
            currSum -= arr[i-1] 
        i -= 1

    return set1, set2 
  
# arr1 = [5,4,1,2]
print_two_equal_sum_sets(arr1)
# A Dynamic Programming solution for rod cutting problem using one array
# Consider the pricing list below for each rod length 1 to 8 inches. If we are given a rod with 8 inches, what
# would be the best cuts we can obtain for most profit. 

price_list = [1, 5, 8, 9, 10, 17, 17, 20]
def rod_cutting_price_optimization1(pricing_list):
    n = len(pricing_list)
    known_results = [0] * (n+1)
    for i in range(1, n+1): # loop over each length possible and store the best value
        best_value = -np.inf
        for j in range(i): # consider each smaller cuts that would fit the capacity
            curr_value = price_list[i-1 - j]
            value_prev_capacity = known_results[j]
            if curr_value + value_prev_capacity > best_value:
                best_value = curr_value + value_prev_capacity    
        known_results[i] = best_value
    print(known_results) # view the whole list for all optinal solutions
    return known_results[n]  

rod_cutting_price_optimization1(price_list)
# A More Simplified Dynamic Programming solution for rod cutting problem using one array

import numpy as np
price_list = [1, 5, 8, 9, 10, 17, 17, 20]
def rod_cutting_price_optimization2(pricing_list):
    n = len(pricing_list)
    prc = np.copy(pricing_list) # np.copy is a deep copy by default
    known_results = np.insert(prc, 0, 0) # array name, index location, object to be inserted
    for i in range(1, n+1):
        for j in range(i): # since each cut is only 1 inches, check the length 
            known_results[i] = max(known_results[i-j] + known_results[j], known_results[i])
    print(known_results) # view the array build up     
    return known_results[n] # view the whole list for all optinal solutions

rod_cutting_price_optimization2(price_list)
# A Dynamic Programming solution for rod cutting problem using a matrix
# Consider the pricing list below for each rod length 1 to 8 inches. If we are given a rod with 8 inches, what
# would be the best cuts we can obtain for most profit. 

import numpy as np
price_list = [1, 5, 8, 9, 10, 17, 17, 20] # i is index

def rod_cutting_optimization3(price_list):
    n = len(price_list) 
    length_list = np.arange(1, len(price_list) + 1) # each rod cut is one inch
    m = len(length_list)
    memo_list = np.zeros([n+1, m+1])
    for i in range(1, n+1):
        for curr_capacity in range(1, m+1):
            curr_item_value = price_list[i-1]
            curr_item_length = length_list[i-1]
            val_at_curr_capacity = memo_list[i-1][curr_capacity]
            if curr_capacity >= curr_item_length: # consider cutting it 
                value_at_prev_capacity = memo_list[i-1][curr_capacity - curr_item_length]
                memo_list[i][curr_capacity] = max(value_at_prev_capacity + curr_item_value, val_at_curr_capacity)
            else: # update the new value with the previous value at max weight
                memo_list[i][curr_capacity] = val_at_curr_capacity
   
    print(memo_list) # view the matrix to see the bottom up approach 
    return memo_list[n][m]

rod_cutting_optimization3(price_list)          

# Dynamic Programming Solution to Word Break Problem.
 
string = "bunniesareawesome"
list_of_substr = ["bunn", "a" , "awesome", "ies", "re"]

# create a function that takes the string and the substring list, outputs if substrings are all found in the string
def word_break(string, words):
    n = len(string)
    # create a memo table
    memo = {i: False for i in range(0, n+1)}
    # assign the start key as True
    memo[0] = True
    for i in range(1, n+1): # traverse the string, index i is starting from 1
        for j in range(i): # traverse each letter until i
            if memo[j] and string[j:i] in words:
                memo[i] = True
                print(memo[j], i, j, string[j:i]) # to view the development of the memo table
                break
    
    return memo[n] 
print(word_break(string, list_of_substr))

# if string was not chosen to exactly made of the substring list but a part of it, the solution would be as follows
# there would be no need for recursion or dp

string = "bunniesadfadfareawesome"
words = ["bunn", "a" , "awesome", "ies", "re"]

# create a function that takes the string and the substring list, outputs if substrings are all found in the string
def words_in_a_string(string, word_list):
    # create a set
    checked_words = set()
    word_list = set(word_list)
    n = len(string)
    for i in range(1, n+1): # traverse the string, index i is starting from 1
        for j in range(i): # traverse each letter until i
            if string[j:i] in word_list and string[j:i] not in checked_words:
                checked_words.add(string[j:i])
    return checked_words == word_list   
    
print(words_in_a_string(string, words))
# Recursive Solution to Word Break Problem.

string = "bunniesareawesome"
list_of_substr = ["bunn", "ies", "awesome", "a" , "re"]

def word_break2(string, list_of_words):
    if string == '': return True
    for i in range(0,len(string)):
        sub = string[:i+1]
        remaining = string[i+1:] # remaining will be: '' 
        if sub in list_of_words and word_break2(remaining, list_of_words):
            return True 
    return False


print(word_break2(string, list_of_substr))<jupyter_output><empty_output><jupyter_text>To be continued with:Longest Common Prefix,Longest Path In Matrix,Optimal Strategy for a Game,Boolean Parenthesization Problem,Shortest Common Supersequence,Maximal Product when Cutting Rope,Dice Throw Problem,Box Stacking,Egg Dropping Puzzle,Longest Palindromic Subsequence,Maximum Subarray Problem THESE WERE USEFUL RESOURCES in creation of this notebook:https://www.geeksforgeeks.org/partition-problem-dp-18/https://www.youtube.com/watch?v=09_LlHjoEiYhttps://www.geeksforgeeks.org/ford-fulkerson-algorithm-for-maximum-flow-problem/  Some matrix operations before the hard problems<jupyter_code># Python3 program to print given matrix in spiral form in a very non-efficient way but in a very easy to code way

import numpy as np
test_m = [[1,2,3,4],
          [5,6,7,8],
          [9,10,11,12]]

# write 2 functions. 
# the first function rotates the matrix, 
# the second one copies the first row and then erases it and calls the first until there is no row to copy
def turn_matrix_counter_clock(m):
    if len(m) == 0: return
    row_length = len(m)
    column_length = len(m[0])
    turned_m = []
    for j in reversed(range(column_length)):
        inner_list = []
        for i in range(row_length):
            inner_list.append(m[i][j])
        turned_m.append(inner_list)
    return turned_m

new_m = turn_matrix_counter_clock(test_m)
print('90 degrees rotated matrix in counter clock wise', new_m)

# print a matrix in spiral form 

def print_m_spiral(m):
    if len(m) == 0: return
    spiral_m = []
    while m != None:
        spiral_m.extend(m[0])
        m_new = m[1:][:]
        m = turn_matrix_counter_clock(m_new)    
    return spiral_m
    
                                 
print_m_spiral(test_m)

# using numpy to rotate a matrix

import numpy as np
m = np.array([[1,2,3,4],
              [2,3,3,5],
              [5,4,3,6]])

def rotate_matrix(mat):
    return np.rot90(mat)
rotate_matrix(m)
# using list comprehension to rotate a matrix and output its elements

new_matrix = [[m[j][i] for j in range(len(m))] for i in range(len(m[0])-1,-1,-1)]
print('rotated matrix', new_matrix)

list_of_items = []
for i in new_matrix:
    list_of_items.extend(i)
print('flatten the rotated matrix', list_of_items)

# rotate a matrix in both directions using list comprehension

m = np.array([[1,2,3,4],
              [2,3,3,5],
              [5,4,3,6]])
counter_clock_90 = [[m[i][j] for i in range(len(m))] for j in reversed(range(len(m[0])))]
print(counter_clock_90)
clockwise_90 = [[m[i][j] for i in reversed(range(len(m)))] for j in range(len(m[0]))]
print(clockwise_90)

# naive 90 degrees turn of a matrix with numpy clockwise

import numpy as np
m = np.array([[1,2,3,4],
              [2,3,3,5],
              [5,4,3,6]])
clockwise_90_deg_array = []
for j in range(len(m[0])):
    inner_list = []
    for i in reversed(range(len(m))): # the elements of the first row is reversed. this will become the rows of new m.
    # the number of rows, this will become the columns
        inner_list.append(m[i][j])
    clockwise_90_deg_array.append(inner_list)

print('result:', clockwise_90_deg_array)

# transpose of a matrix:

# with list comprehension
MT = [[row[i] for row in m] for i in range(len(m))]
print(MT)

# with naive approach
transpose = np.zeros([len(m[0]), len(m)])
for i in range(len(m)): # for each item in the row
    for j in range(len(m[0])): # for each item in the column
        transpose[j][i] = m[i][j]
print(transpose)

# with numpy package
transpose_np = np.zeros([len(m[0]), len(m)])
for i in range(len(m)):
    for j in range(len(m[0])):
        transpose_np[j][i] = m[i][j]
print(transpose_np)

# with numpy built-in function
transpose_with_np = np.transpose(m)
print(transpose_with_np)<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.09549914343560194, 'fraction_numerical': 0.019903441831490423, 'mean_word_length': 2.779399646851089, 'pattern_counts': {'":': 1, '<': 22, '<?xml version=': 0, '>': 29, 'https://': 3, 'lorem ipsum': 0, 'www.': 3, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '2', 'dir': 'jupyter-structured-clean-dedup', 'id': '370411', 'license': 'MIT', 'n_tokens_mistral': 10678, 'n_tokens_neox': 10120, 'n_words': 3673, 'path': 'Dynamic_Programming_1.ipynb', 'repo_name': 'volkansonmez/Dynamic_Programming', 'size': '32105'}