## Table of contents

- Dynamic programming (Overlapping property)
- Top down with Memoization
- Bottom up with Tabulation
- Top Down vs Bottom Up
- Is Merge Sort dynamic programming?
- Number Factor: Top down and Bottom up
- House Robber : Top down and Bottom up
- Convert String using Bottom Up
- Zero one knapsack - Top down
- Zero one knapsack - Bottom up
- End.

Did you know that dynamic programming is a very old concept (the name was given by Bellman) and the word "programming" here has nothing to do with writing code? Instead, it focuses on finding the optimal solution. Believe it or not, dynamic programming is a powerful tool. It's like a cheat code for lazy coders. But enough talk, let's get started!

Disclaimer : The questions given here were described in my previous blog. So, if you're facing problem to understand them - have a look at Divide & Conquer Algorithm

*Dynamic programming (Overlapping property)*

Dynamic programming (DP) is an algorithm technique that solves an optimization problem by breaking it into simpler subproblems, using the optimal solutions of these subproblems to find the overall solution.

Imagine we want to solve a series.

In this case which is 7. Now, we want to solve another series.

Basically what we are going to do here is - take 7 from the previous solution and add it with 2. Instead of adding 7 ones again, we are just using the answer from before.

When we break a problem into smaller parts, we often see the same parts appearing again and again. Instead of solving them each time, we solve them once, store the solution, and reuse it as needed.

DP has two properties:

Optimal Substructure:

If any problem's overall optimal solution can be constructed from the optimal solutions of its subproblem then this problem has optimal substructure.

Example : Fib(n) = Fib(n-1) + Fib(n-2)

Overlapping Subproblem:

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

*Top down with Memoization*

Solve the bigger problem by recursively finding the solution to smaller subproblems. 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. The technique of storing the results of already solved subproblems is called **Memoization**. This helps to improve space and time complexity.

Here's a code for 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)
myDict = {}
print(findMemo(6, myDict))
```

*Bottom up with Tabulation*

Tabulation is the opposite of the top-down approach and avoids recursion. In this method, we solve the problem "bottom-up" by first solving all the related subproblems. This is done by filling up a table. Based on the results in the table, we then compute the solution to the original problem.

```
def fibonacciTab(n):
tb = [0,1]
for i in range(2, n+1):
tb.append(tb[i-1]+tb[i-2])
return tb[n-1]
print(fibonacciTab(6))
```

*Top Down vs Bottom Up*

Top down | Bottom up | |

Easiness | Easy to come up with solution as it is extension of divide and conquer | Difficult to come up with 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 |

*Is Merge Sort dynamic programming?*

First, let me ask - How do you identify Dynamic problem? Well, you identify it based on two properties -

Does it have Optimal structure property?

Does it have Overlapping Subproblems property?

Now think about merge sort properties. I hope you got your answer -

No, Merge Sort is not dynamic programming. It’s a divide-and-conquer algorithm. Merge Sort **works by recursively dividing the array into smaller subarrays, sorting each subarray, and then merging them back together.** Dynamic programming, on the other hand, involves solving problems by breaking them into overlapping subproblems and storing their solutions to avoid redundant work.

*Number Factor: Top down and Bottom up*

```
def numberFactorTD(n, tempDict):
if n in (0,1,2):
return 1
elif n == 3:
return 2
else:
if n not in tempDict:
subP1 = numberFactorTD(n-1, tempDict)
subP2 = numberFactorTD(n-3, tempDict)
subP3 = numberFactorTD(n-4, tempDict)
tempDict[n] = subP1 + subP2 + subP3
return tempDict[n]
#bottom up
def numberFactorBU(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(numberFactorBU(5))
```

*House Robber : Top down and Bottom up*

```
#top down
def houseRobberTD(houses, currentIndex, tempDict):
if currentIndex >= len(houses):
return 0
else:
if currentIndex not in tempDict:
stealFirstHouse = houses[currentIndex] + houseRobberTD(houses, currentIndex+2, tempDict)
skipFirstHouse = houseRobberTD(houses, currentIndex+1, tempDict)
tempDict[currentIndex] = max(stealFirstHouse, skipFirstHouse)
return tempDict[currentIndex]
houses = [6,7,1,30,8,2,4]
print(houseRobberTD(houses, 0, {}))
#bottom up
def houseRobberBU(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]
print(houseRobberBU(houses,0))
```

*Convert String using Bottom Up*

**Problem Statement**

S1 and S2 are given strings

Convert S2 to S1 using

*delete*,*insert*or*replace*operationsCreate a function using Bottom Up approach to find the minimum count of edit operations

**Example :** findMinOperationBU("table", "tbrltt", {}) #4

```
def findMinOperationBU(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]
```

*Zero one knapsack - Top down*

Given the *weights* and *profits* of **N items** and these items cannot be broken into the pieces. Create a function to find the maximum profit within given *capacity* of **C** using **Top Down method**.

**Example**

*Input:*

*profits = [ 31, 26, 72, 17 ]*

*weights = [ 3, 1, 5, 2 ]*

*capacity = 7*

```
zoKnapsack(items, 7, 0, {}) #98
```

```
# Zero One Knapsack Problem
class Item:
def __init__(self, profit, weight):
self.profit = profit
self.weight = weight
def zoKnapsack(items, capacity, currentIndex, tempDict):
#todo
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 + zoKnapsack(items, capacity-items[currentIndex].weight, currentIndex+1, tempDict)
profit2 = zoKnapsack(items, capacity, currentIndex+1, tempDict)
tempDict[dictKey] = max(profit1, profit2)
return tempDict[dictKey]
else:
return 0
```

*Zero one knapsack - Bottom up*

Given the *weights* and *profits* of **N items** and these items cannot be broken into the pieces. Create a function to find the maximum profit within given *capacity* of **C** using **Bottom Up method**.

**Example**

*Input:*

*profits = [ 31, 26, 72, 17 ]*

*weights = [ 3, 1, 5, 2 ]*

*capacity = 7*

```
zoKnapsackBU(profits, weights, capacity) #98
```

```
def zoKnapsackBU(profits, weights, capacity):
#todo
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]
```