Dynamic Programming in Python

I am going to solve three problems with dynamic programming (DP) in this tutorial. Dynamic programming is a technique used in mathematics and programming to solve complex problems fast. A DP-problem is solved by breaking it down into subproblems, each subproblem is solved once and solutions to subproblems is stored to be retrieved later.

A dynamic programming problem must have an optimal substructure and overlapping subproblems. A problem with non-overlapping subproblems is usually solved with a divide-and-conquer strategy instead of DP. A problem have an optimal substructure if the solution can be found by combining optimal solutions to subproblems. A problem with overlapping subproblems have subproblems that must be solved several times in order to find the optimal solution, solutions to overlapping subproblems can be stored and reused to save time an make the code faster.

The DP-method was invented in 1953 by Richard Bellman and has applications in mathematics, engineering and bioinformatics for example. Dynamic programming is based on a Bellman equation, it is a state-value function used to maximize the value of the next state given the current state.

Fibonacci Sequence

This problem is about to generate a sequence of fibonacci numbers, the function takes the size of the sequence as input. Every generated fibonacci number is saved to an array and can be reused later, output from a run is shown below the code.

# Generate a fibonacci sequence
def fibonacci_sequence(n:int) -> []:

    # Create an array
    numbers = []

    # Loop n numbers
    for i in range(n):
        if i < 2:
            numbers.append(i)
        else:
            numbers.append(numbers[i - 2] + numbers[i - 1])

    # Return fibonacci numbers
    return numbers

# The main entry point for this module
def main():

    # Generate a fibonacci sequence
    print('Fibonacci sequence, {0} numbers: {1}'.format(20, fibonacci_sequence(20)))
    print()

# Tell python to run main method
if __name__ == '__main__': main()

Fibonacci sequence, 30 numbers: [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229]

Longest Increasing Subsequence

This problem is about to find the longest increasing subsequence of numbers given a sequence of numbers. The algorithm takes each number in order and adds it to a subsequence, a number that is encountered in the input list can not be added before already added numbers. Output from a run is shown below the code.

# Import libraries
import numpy as np

# Get longest increasing subsequence
def get_lis(sequence:[]) -> []:

    # Variables
    n = len(sequence) 
    max_length = 0
    lis = np.ones(n, dtype='int')

    # Get lis lengths
    for i in range (1 , n): 
        for j in range(0 , i): 
            if sequence[i] > sequence[j] and lis[i] < lis[j] + 1 : 
                lis[i] = lis[j]+1
  
    # Get the maximum length
    for i in range(n): 
        max_length = max(max_length, lis[i]) 
  
    # Return the solution
    return max_length

# The main entry point for this module
def main():

    # Generate longest increasing subsequence
    print('Longest increasing subsequence: {0}'.format(get_lis([10, 22, 9, 33, 21, 50, 41, 60, 80])))
    print()

# Tell python to run main method
if __name__ == '__main__': main()

Longest increasing subsequence: 6

Knapsack Problem

This problem is about optimizing the value of items in a knapsack given a weight constraint. The knapsack can handle a certain weight and you have a number of items with weights and values that you want to pack in the knapsack. The goal is to find the maximum value of items in the knapsack, output from a run is shown below the code.

# Get a knapsack solution
def knapsack(max_weight:int, weights:[], values:[]) -> int:

    # Get the length
    n = len(weights)

    # Create a matrix
    matrix = [[0 for w in range(max_weight + 1)] for i in range(n + 1)]

    # Loop max weight
    for w in range(max_weight + 1):

        # Loop all weights and values
        for i in range(n + 1):

            # Add value to matrix
            if (w == 0 or i == 0):
                matrix[i][w] = 0
            elif weights[i-1] <= w:
                matrix[i][w] = max(values[i-1] + matrix[i-1][w-weights[i-1]], matrix[i-1][w])
            else:
                matrix[i][w] = matrix[i-1][w]

    # Return best value
    return matrix[n][max_weight]

# The main entry point for this module
def main():

    # Solve knapsack problem
    print('Best value in knapsack: {0}'.format(knapsack(15, [3,2,4,6,8], [30,20,40,60,80])))
    print()

# Tell python to run main method
if __name__ == '__main__': main()

Best value in knapsack: 150