Dynamic Programming

  

Today in class we discussed how in certain circumstances the recursive approach of solving a problem does way more work than required. In the case of generating the Fibonacci sequence, the recursive method was doing the same calculations over and over, making the solution to the problem very inefficient. This is where the dynamic programming approach was introduced. Such approach "memorizes" the solutions to the sub problems and whenever the algorithm encounters such a problem again it simply looks up the solution in the solution collection (such as list or dictionary). As expected, the new approach (still recursive, but a smarter one) increased the efficiency of the algorithm. 

I used a similar technique for assignment 1.

We had to find out the best split of cheeses in order to move all the cheeses form first stool to the last one using four stools.  My method stored the best split of cheeses in the increasing order starting from 3 (cheeses) making available all the solutions required for each next number of cheeses. 

Below is my actual implementation of the method. 

# A dictionary that contains the best split (i) and the minimum number of

# moves it takes to move n cheeses using 4 stools for any n cheeses.

# The dictionary contains the required values once best_partition(n)

# is executed.

library = {1: [0, 1], 2: [1, 3]}

def best_partition(n: int) -> list:

    """

    For a given number of cheeses find and return a list that contains the

    best split (starting from the bottom) and the minimum number of moves it

    takes to move all the cheeses using 4 stools.

    For example to move 7 cheeses it's best to split them at i = 3 and this

    takes 25 moves, so:

    >>> best_partition(7)

    [3, 25]

    """

    if(n in library):

        return library[n]

    else:

        # Next number of cheeses missing in the library

        next_n = len(library) + 1

        # Steps it would take if 3 stools were used.

        min_steps = (2 ** next_n) - 1

        # Find the lowest number of steps and record the best split

        # together with the number of steps taken for the best split.

        for rep in range(next_n - 1):

            i = rep + 1

            steps = (2 ** i) - 1 + 2 * ((best_partition(next_n - i))[1])

            if(steps < min_steps):

                min_steps = steps

                library[next_n] = [i, min_steps]

        best_partition(n)

        return library[n]