It's Dynamic Programming, Lazy Coder's Best Friend!

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 operations
Create 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.