Dynamic Programming

Don't redo, just reuse

In this blog Im just showing a map to climb the hill (way to dynamic programming).

Passages are also important like your browser history, don't ignore it.

How to write Dynamic programming?

By dividing the large program into a sub-program. If possible sub-program into sub-sub-Program and sub-sub-sub on…..

So one can avoid some overlapping sub-program or similar sub-program results can be re-used

Yes, you’re not clear. Okay, you can solve dynamic programming using any of these three methods.

• Recursion
• store (memoize) or Top-down
• Bottom-up ( If you bored with recursion)

Using the Fibonacci series as an example. Hope you known about Fibonacci series

Recursion

Directly to the algorithm (Normal Fibonacci series using recursion)

Normal Fibonacci series using recursion

let’s look at how this algorithm works with a flow chart when n = 5

This is how the program will run and get the output as 5 when n = 5 .

yes, it is more optimized than the normal method.

But here look at fibonacci (3) we got twice and calculated fibonacci (3) twice.

Here we need to think in a dynamic way, we calculate fibonacci (3)only once and reuse it when we need it in another place. And that is known as memoizing

Memoizing or Top-down

In simple words memorizing is storing the previous output and input for future use. If the same input passed, we don’t want to calculate it because we know the answer ( just using the previous output)

Thank god we saved some operations and our compiler work

Okay let me show the algorithm with memorizing

So here we will be storing the series results in anything like an array or dictionary. Before getting into the operation we will be checking whether this input already exists or not in the storage. if excite will be returning the stored output of that input.

example: Fibonacci (3) occurs twice, so here we will store the Fibonacci (3) output in an array while occurring the first time. When Fibonacci (3) occurs for the second time we will return the result that already stored

Look at the algorithm and the flow way for more understanding

so here we will be storing every result in memoStorage

memoStorage the array will be transforming like

memoizeMethod.swift

var memo = [Int: Int]() 
//in swift, if declared the dictionary outside the func only I //getting in the correct
func fib (_ num: Int) -> Int {
if let cached = memo[num] {
return cached
}
let result: Int
if (num <= 2) {
result = 1
}
else {
result = fib(num - 1) + fib(num - 2)
}
memo[num] = result
return result
}
print(fib(5))

Bottom-up Approach

It is a normal Approach like finding fibonacci[1] first and then fibonacci[2] then fibonacci[3] and so on…. (Then we will use the memorize Method )

one thing is good here, No recursion.

transformation of the dictionary in this algorithm

BottomUpApproach.swift

func bottomUp(n: Int) -> Void {
var result = 0
var bottomUp = [1: 1, 2: 1]
for i in 3..<n + 1 {
bottomUp[i] = ( bottomUp [i - 1] ?? 0) + ( bottomUp [i - 2] ?? 0 )
print(bottomUp)
}
result =  bottomUp[n] ?? 0
print(bottomUp[5])
}
bottomUp(n: 5)

So you might try hard to climb the hill.

Don’t redo, just reuse

Tony Wilson Jesuraj