Dynamic Programming in Python

Dynamic Programming(DP) is an algorithmic technique for solving an optimization problem by breaking it down into simpler subproblems and utilizing the fact that the optimal solution to the overall problem depends upon the optimal solution to the subproblems.

If an issue can be broken down into subproblems, which are then broken down into smaller subproblems, and if these subproblems overlap, the answers to these subproblems can be preserved for future use.

Dynamic programming works by saving the results of subproblems so that we don’t have to recalculate them when their solutions are needed.

Example: Fibonacci Series

Optimal Substructure: If any problem’s overall optimal solution can be constructed from the optimal solutions of its subproblem, then this problem has an optimal substructure.
Fibonacci(N) = Fibonacci(N-1) + Fibonacci(N-2)

Overlapping Subproblem: Subproblems are smaller versions of the original problem. Any problem has overlapping subproblems if finding its solution involves solving the same subproblem multiple times.

Table of Contents

1. Top Down Approach with Memoization

1.1. Implementation of Fibonacci Series using Memoization

1.1.1. Fibonacci Series Algorithm

2. Bottom Up Approach with Tabulation

2.2. Implementation of Fibonacci Series using Tabulation

2.2.2. Fibonacci Series Algorithm

3. Top-Down Approach vs Bottom-Up Approach

4. Number Factor

4.3. Implementation of Number Factor using Top Down Approach

4.4. Implementation of Number Factor using Bottom Up Approach

5. House Robber

5.5. Implementation of House Robber using Top Down Approach

5.6. Implementation of House Robber using Bottom Up Approach

6. Convert String

6.7. Implementation of String Convert using Top Down Approach

6.8. Implementation of String Convert using Bottom Up Approach

7. Zero One Knapsack Problem

7.9. Implementation of Zero One Knapsack Problem using Top Down Approach

7.10. Implementation of Zero One Knapsack Problem using Bottom Up Approach

Top Down Approach with Memoization

Whenever we solve a subproblem, we cache its result so that we don’t end up solving it repeatedly if it’s called multiple times. This technique of storing the results of the previously solved subproblems is called Memoization.

In memoization, we solve the bigger problem by recursively finding the solution to the subproblems. It is a top-down approach.

Implementation of Fibonacci Series using Memoization

The Fibonacci Series is a series of numbers in which each number is the sum of the preceding two numbers. By definition, the first two numbers are 0 and 1.

Example: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55,…….

Fibonacci Series Algorithm

Fibonacci Series can be implemented using Memoization using the following steps:

Declare the function and take the number whose Fibonacci Series is to be printed and a dictionary memo as parameters.
If n equals 1, return 0.
If n equals 2, return 1.
If the current element is memo, add it to the memo by recursivel calling the function for the previous to values and adding them.

# Function to implement Fibonacci Series
def fibMemo(n, memo):
    if n == 1:
        return 0
    if n == 2:
        return 1
    if not n in memo:
        memo[n] = fibMemo(n-1, memo) + fibMemo(n-2, memo)
    return memo[n]

tempDict = {}
fibMemo(6, tempDict)

#Printing the elements of the Fibonacci Series
print("0")
print("1")
for element in tempDict.values():
    print(element)

Output

Bottom Up Approach with Tabulation

Tabulation is the opposite of the top-down approach and does not involve recursion. In this approach, we solve the problem “bottom-up”. This means that the subproblems are solved first and are then combined to form the solution to the original problem.

This is achieved by filling up a table. Based on the results of the table, the solution to the original problem is computed.

Implementation of Fibonacci Series using Tabulation

Example: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55,…….

Fibonacci Series Algorithm

Fibonacci Series can be implemented using Tabulation using the following steps:

Declare the function and take the number whose Fibonacci Series is to be printed.
Initialize the list and input the values 0 and 1 in it.
Iterate over the range of 2 to n+1.
Append the list with the sum of the previous two values of the list.
Return the list as output.

# Function to implement Fibonacci Series
def fibTab(n):
    tb = [0, 1]
    for i in range(2, n+1):
      tb.append(tb[i-1] + tb[i-2])
    return tb

print(fibTab(6))

#Output
[0, 1, 1, 2, 3, 5, 8]

Top-Down Approach vs Bottom-Up Approach

	Top-Down	Bottom-Up
Easiness	Easy to solve as it is an extension of Divide and Conquer	Difficult to come up with a solution
Runtime	Slow	Fast
Space Efficiency	Unnecessary use of stack space	Stack is not used
When to use	Need a quick solution	Need an efficient solution

Number Factor

We are given a number N. Find the number of ways of expressing N as a sum 1, 3, and 4.

Example:
– N = 5
– Number of ways = 6
– Explanation: There are 6 ways to express N. {4,1}, {1,4}, {1,3,1}, {3,1,1}, {1,1,3}, {1,1,1,1,1}

Implementation of Number Factor using Top Down Approach

Number Factor problem can be implemented using the Top-Down Approach in the following manner:

Declare the function and take the number whose Number Factor is to be printed and a temporary dictionary as parameters.
If the number is 0, 1, or 2, return 1.
Else, if the number is 3, return 2.
Else, recursively call the function for three sub-parts N-1, N-3, N-4.
Assign the sum of the three sub-parts to the dictionary.
Return the last element of the dictionary as output.

#Function to solve Number Factor Problem
def numberFactor(n, tempDict):
    if n in (0,1,2):
        return 1
    elif n == 3:
        return 2
    else:
        subPart1 = numberFactor(n-1, tempDict)
        subPart2 = numberFactor(n-3, tempDict)
        subPart3 = numberFactor(n-4, tempDict)
        tempDict[n] = subPart1+subPart2+subPart3
        return tempDict[n]

print(numberFactor(5, {}))

#Output
6

Implementation of Number Factor using Bottom Up Approach

Number Factor problem can be implemented using the Bottom-Up Approach in the following manner:

Declare the function and take the number whose Number Factor is to be printed as parameter.
Initialize an array with the values 1, 1, 1, 2.
Iterate over the range from 4 to n+1.
Append the array with the sum of the values at indices – i-1, i-3, i-4.
Return the last element of the array.

#Function to solve Number Factor Problem
def numberFactor(n):
   tempArr = [1,1,1,2]
   for i in range(4, n+1)
       tempArr.append(tempArr[i-1]+tempArr[i-3]+tempArr[i-4])
       return tempArr[n]

print(numberFactor(5))

#Output
6

House Robber

We are given N number of houses along a street, each having some amount of money. A thief can not steal from adjacent houses. Find the maximum amount that can be stolen.

Example:

Answer:
– Maximum amount = 41
– Houses Stolen = 7, 30, 4

Implementation of House Robber using Top Down Approach

House Robber problem can be implemented using the Top-Down Approach in the following manner:

Declare the function and take the houses, current index, and a temporary dictionary as parameters.
If the currentIndex is greater than the length of the list of houses, return 0.
Then, we create two lists – stealFirstHouse and skipFirstHouse.
We recursively call the function for each variable by incrementing the index.
Finally, the max value between the two sets is assigned to the current index of the dictionary.
Return the value at the current index of the dictionary.

#Function to solve House Robber Problem
def houseRobber(houses, currentIndex, tempDict):
    if currentIndex >= len(houses):
        return 0
    else:
        stealFirstHouse = houses[currentIndex] + houseRobber(houses, currentIndex + 2, tempDict)
        skipFirstHouse = houseRobber(houses, currentIndex+1)
        tempDict[currentIndex] = max(stealFirstHouse, skipFirstHouse, tempDict)
        return tempDict[currentIndex]
 
houses = [6,7,1,30,8,2,4]
print(houseRobber(houses, 0, {}))

#Output 
41

Implementation of House Robber using Bottom Up Approach

House Robber problem can be implemented using the Bottom-Up Approach in the following manner:

Declare the function and take the houses and current index as parameters.
Initialize a temporary array with all the elements set to zero.
Iterate over the list of houses by decrementing the indices.
In the current index of the array, store the maximum of the following two values – houses[i] + tempArr[i+2], tempArr[i+1].
Return the first element of the array as output.

#Function to solve House Robber Problem  
def houseRobber(houses, currentIndex):
    tempArr = [0] * (len(houses)+2)
    for i in range(len(houses)-1, -1, -1):
        tempArr[i] = max(houses[i] + tempArr[i+2], tempArr[i+1])
    return tempArr[0]  
 
houses = [6,7,1,30,8,2,4]
print(houseRobber(houses, 0))

#Output 
41

Convert String

We are given two strings S1 and S2. Convert S2 to S1 using delete, insert or replace operations. Find the minimum number of edit operations

Example:
– S1 = “table”
– S2 = “tbres”
– Output = 3
– Explanation: Insert “a” to second position, replace “r” with “l”, and delete “s”.

Implementation of String Convert using Top Down Approach

String Convert problem can be implemented using the Top-Down Approach using the following steps:

Declare the function and take the strings s1 and s2, along with their starting indices and a temporary dictionary as parameters.
If s1 or s2 are empty strings, return the differnece between the empty string and the other string as output.
If they have the same length, recursively invoke the function by incementing the index.
Declare dictKey as the sum of the two indices in string format.
Else, recursively invoke the function for each seperate operation by incrementing the value of the indices.
Assign the minimum of the three values to the dictionary at dictKey.

#Function to solve String Convert Problem
def findMinOperation(s1, s2, index1, index2, tempDict):
    if index1 == len(s1):
        return len(s2)-index2
    if index2 == len(s2):
        return len(s1)-index1
    if s1[index1] == s2[index2]:
        return findMinOperation(s1, s2, index1+1, index2+1)
    else:
        dictKey = str(index1) + str(index2)
        if dictKey not in tempDict:
            deleteOp = 1 + findMinOperation(s1, s2, index1, index2+1)
            insertOp = 1 + findMinOperation(s1, s2, index1+1, index2)
            replaceOp = 1 + findMinOperation(s1, s2, index1+1, index2+1)
            tempDict[dictKey] = min (deleteOp, insertOp, replaceOp)
        return tempDict[dictKey]

print(findMinOperation("table", "tbres", 0, 0))

#Output
3

Implementation of String Convert using Bottom Up Approach

String Convert problem can be implemented using the Bottom-Up Approach using the following steps:

Declare the function and take the strings s1 and s2, and a temporary dictionary as parameters.
Iterate over the first string s1 and create key-value pairs using the indices of the string. Store it in the temporary dictionary.
Iterate over the second string s2 and create key-value pairs using the indices of the string. Store it in the temporary dictionary.
Create a nested loop and iterate over the two given strings.
Compare the values of the associated elements of the strings. For each comparison and operation count, and create new key-value pairs for each.
Finally, chose the dictionary key with the minimum value and return it as output.

#Function to solve String Convert Problem
def findMinOperation(s1, s2, tempDict):
    for i1 in range(len(s1)+1):
        dictKey = str(i1)+'0'
        tempDict[dictKey] = i1
    for i2 in range(len(s2)+1):
        dictKey = '0'+str(i2)
        tempDict[dictKey] = i2

    for i1 in range(1, len(s1)+1):
        for i2 in range(1, len(s2)+1):
            if s1[i1-1] == s2[i2-1]:
                dictKey = str(i1)+str(i2)
                dictKey1 = str(i1-1)+str(i2-1)
                tempDict[dictKey] = tempDict[dictKey1]
            else:
                dictKey = str(i1)+str(i2)
                dictKeyD = str(i1-1)+str(i2)
                dictKeyI = str(i1)+str(i2-1)
                dictKeyR = str(i1-1)+str(i2-1)
                tempDict[dictKey] = 1 + min(tempDict[dictKeyD],
                                            min(tempDict[dictKeyI], tempDict[dictKeyR]))
    dictKey = str(len(s1))+str(len(s2))
    return tempDict[dictKey]

print(findMinOperation("table", "tbres", {}))

#Output
3

Zero One Knapsack Problem

We are given the weights and profits of N items. Find the maximum profit if we are given the knapsack capacity C. Items cannot be broken and must be added fully.

Example:

Answer:
Max profit is achieved by the following combination:

Apple(W: 1, P: 26) + Banana(W: 5, P: 72) = W: 6, P: 98

Implementation of Zero One Knapsack Problem using Top Down Approach

For the implementation of the Zero Knapsack Problem, we first create the Item where each object holds two variables – weight and profit.

Zero One Knapsack Problem can be implemented using the Top-Down Approach in the following manner:

Declare the function and take the items, capacity, a temporary dictionary, and current index as parameters.
If capacity is less than 0, currentIndex is less than 0, or currentIndex is greater than length of the list, return 0.
Else, if the total weight is less than the capacity, create two profits for checking adajacent items. This is achieved by recursively calling the function with different parameters.
Assign the maximum out of these two profitsto the current element of the dictionary.
Return that value of the dictionary as output.

#Function to solve Zero One Knapsack Problem
class Item:
    def __init__(self, profit, weight):
        self.profit = profit
        self.weight = weight
        
def zeroKnapsack(items, capacity, currentIndex, tempDict):
    dictKey = str(currentIndex) + str(capacity)
    if capacity <= 0 or currentIndex < 0 or currentIndex >= len(items):
        return 0
    elif dictKey in tempDict:
        return tempDict[currentIndex]
    elif items[currentIndex].weight <= capacity:
        profit1 = items[currentIndex].profit + zeroKnapsack(
            items, capacity-items[currentIndex].weight, currentIndex+1, tempDict)
        profit2 = zeroKnapsack(items, capacity, currentIndex+1, tempDict)
        tempDict[dictKey] = max(profit1, profit2)
        return tempDict[dictKey]
    else:
        return 0
        
mango = Item(31, 3)
apple = Item(26, 1)
orange = Item(17, 2)
banana = Item(72, 5)

items = [mango, apple, orange, banana]

print(zeroKnapsack(items, 7, 0, {}))

#Output
98

Implementation of Zero One Knapsack Problem using Bottom Up Approach

For the implementation of the Zero Knapsack Problem, we first create the Item where each object holds two variables – weight and profit.

Zero One Knapsack Problem can be implemented using the Bottom-Up Approach in the following manner:

Declare the function and take the profts, weights of the items, and the knapsack capacity as parameters.
If the capacity is less than 0, length of profits equals 0, or the length of the profits and weights are not same, return 0.
Create variables – numberOfRows and dp. Iterate over number of rows and capacity, initializing the values of dp to 0.
Create two variables for storing profits. Store the values for each row and column of the matrix dp as long as its weight does not exceed capacity.
Repeat the process and return the max of the two variables as output.

#Function to solve Zero One Knapsack Problem
class Item:
    def __init__(self, profit, weight):
        self.profit = profit
        self.weight = weight

def zoKnapsackBU(profits, weights, capacity):
    if capacity <= 0 or len(profits) == 0 or len(weights) != len(profits):
        return 0
    numberOfRows = len(profits) + 1
    dp = [[None for i in range(capacity+2)] for j in range(numberOfRows)]
    for i in range(numberOfRows):
        dp[i][0] = 0
    for i in range(capacity+1):
        dp[numberOfRows-1][i] = 0
    for row in range(numberOfRows-2, -1, -1):
        for column in range(1, capacity+1):
            profit1 = 0
            profit2 = 0
            if weights[row] <= column:
                profit1 = profits[row] + dp[row + 1][column - weights[row]]
            profit2 = dp[row + 1][column]
            dp[row][column] = max(profit1, profit2)
    return dp[0][capacity]

profits = [31, 26, 17, 72]
weights = [3, 1, 2, 5]

print(zoKnapsackBU(profits, weights, 7))

#Output
98

Dynamic Programming in Python

Top Down Approach with Memoization

Implementation of Fibonacci Series using Memoization

Fibonacci Series Algorithm

Bottom Up Approach with Tabulation

Implementation of Fibonacci Series using Tabulation

Fibonacci Series Algorithm

Top-Down Approach vs Bottom-Up Approach

Number Factor

Implementation of Number Factor using Top Down Approach

Implementation of Number Factor using Bottom Up Approach

House Robber

Implementation of House Robber using Top Down Approach

Implementation of House Robber using Bottom Up Approach

Convert String

Implementation of String Convert using Top Down Approach

Implementation of String Convert using Bottom Up Approach

Zero One Knapsack Problem

Implementation of Zero One Knapsack Problem using Top Down Approach

Implementation of Zero One Knapsack Problem using Bottom Up Approach

Trending Posts You Might Like