Knapsack - no DP, top down, and bottom up

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]
        
# for this one, we don't need a helper. we're computing the memo array with a for loop, so there's no recursive calls passing around   
def knapSackBottomUp(n: int, values: list, weights: List, W: int) -> int:
    # base case, no trick question here
    if n <= 0 or W <= 0:
        return 0
    T = [[0] * (W + 1) for i in range(n +1)]
    
    # now we're going to iteratively fill up the memoized array by recursively storing the sub problems - all we have to do is 'look' at the previous cell if we take it because the previous cell (i - 1) stores the 'accumulated' subproblems
    # iterate through the items (same array as the top down) from 0 to n (aka, n + 1 cuz range is not inclusive)
    for i in range(n + 1):
        for w in range(W + 1):
            index = i - 1 # remember, not n - 1. it's BOTTOM up, NOT top down. we are NOT peeling away like we usually do with the divide and conquer approach
            
            take_it, leave_it = 0, 0
            
            if weights[index] < w:
                take_it = values[index] + T[index - 1][w - weights[index]]
            
            leave_it = T[index - 1][w]
            
            T[i][w] = max(take_it, leave_it)
            
    return T[i][w]
    
    
        
    
    

no_dp = knapsackNoMemoization(5, [300, 34, 20, 15, 100], [3, 10, 2, 1, 10], 10)
dp_top_down = knapSackTopDown(5, [300, 34, 20, 15, 100], [3, 10, 2, 1, 10], 10)
dp_bottom_up = knapSackTopDown(5, [300, 34, 20, 15, 100], [3, 10, 2, 1, 10], 10)
    
print(f'no dp is {no_dp}.\ndp_top_down is {dp_top_down}.\n dp_bottom_up is {dp_bottom_up}' )