# 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.

### 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]``````

### 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:

– 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 =  * (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

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:

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
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[capacity]

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

print(zoKnapsackBU(profits, weights, 7))

#Output
98``````