Fixed top down

from typing import List


    # the code to the knapsack problem with no memoization, only recursion
def knapsackNoMemoization(n, values: List, weights: List, W) -> int:
        # base case, if there's no items left or the weight constraint is now 0
        if n == 0 or W == 0:
            return 0
        
        # each refers to taking or leaving the last item (divide and conquer, remember?)
        take_it, leave_it = 0, 0
        
        # the last index is n - 1, we're using this to make the code a little more readable. at each step, we're 'peeling' away the last index.
        index = n - 1 
        
        # the 'take it' case - assuming it fits into the knapsack, do we include the item and decrement the weight or not?
        if weights[index] <= W:

            # the logic for this is if we take the item, we take it, and add it to the maximimum amount solved later in the sub problems
            take_it = values[index] + knapsackNoMemoization(n - 1, values, weights, W - weights[index])

        # otherwise, we leave it (so don't adjust weight)
        leave_it = knapsackNoMemoization(n - 1, values, weights, W)
        # then we constantly just try to take the max of both, basically asking ourselves, 'hey, is it more profitable to include it and look at the rest of the bag? or what if we don't include it because it doesn't fit and look at the rest of the bag?'
        return max(take_it, leave_it)


    # The top down approach is EXACTLY THE SAME as the divide and conquer approach, but we have to now store the n x W subproblems as a 2D array.

def knapSackTopDown(n: int, values: List, weights: List, W: int) -> int:

    T = [[None] * (W + 1) for _ in range(n + 1)]
    
    return knapsackTopDownDPHelper(n, values, weights, W, T)

def knapsackTopDownDPHelper(n: int, values: List, weights: List, W: int, T: List[List]) -> int:
    if n <= 0 or W <= 0:
        return 0
    
    # the reason we use n and W is they will be decremented over time with each recursive call
    # anyways, if the solution has been stored, just retrieve it
    if T[n][W] is not None:
        return T[n][W]
    
    # initializing the two possible cases (aka, how do our 2^n search)
    take_it, leave_it = 0, 0
    # still stripping away the last element for each sub problem / recursive call
    index = n - 1
    
    if weights[index] <= W:
        take_it = values[index] + knapsackTopDownDPHelper(n - 1, values, weights, W - weights[index], T)
        
    leave_it = knapsackTopDownDPHelper(n - 1, values, weights, W, T)

    T[n][W] = max(take_it, leave_it)
    
    return T[n][W]
        

import time

start1 = time.time()
no_dp = knapsackNoMemoization(5, [300, 34, 20, 15, 100], [3, 10, 2, 1, 10], 10)
end1 = time.time()

start2 = time.time()
dp = knapSackTopDown(5, [300, 34, 20, 15, 100], [3, 10, 2, 1, 10], 10)
end2 = time.time()
    
print(f'no dp is {no_dp}, Time for no DP: {end1 - start1}. dp is {dp}, Time for DP: {end2 - start2}')