Dynamic programming technique tries to compute and store solutions to smaller sub-problems first and then slowly builds solution to the original problem by combining results of the intermediate sub-problems.
Difference Between Recursion and Dynamic Programming
This methodology seems similar to recursion and Memoization techniques, but there’s one major difference. Dynamic programming is a type of “bottom up approach” where as recursion is a kind of “top down approach”.
Dynamic programming (bottom up approach), tries to start with the smallest sub-problem first and then slowly combines results for these sum-problems until we get to the original problem.
Recursion technique (top-down approach) starts from the bigger problem first, which is then split into multiple sub problems and each one is solved independently and then combined.
Finding Nth Number in a Fibonacci Sequence Using Recursion
Let’s consider the example of finding nth number in a Fibonacci sequence. This is how we do it recursively:
fun fibonacci(n):
if n == 0 or n == 1: # Base Case
return 1
else:
return fibonacci(n-2) + fibonacci(n-1)
We first start with the bigger problem of finding nth Fibonacci digit and then recursively find and combine the results of Fibonacci digits n-2 and n-1.
Finding Nth Number in a Fibonacci Sequence Using Dynamic Programming
In Dynamic Programming, we first start with the basic sub-problem Fibonacci(0) and Fibonacci(1) for which we know the results (1 & 1) and then build the series until we reach the nth sequence.
fibonacci_sequence = []
fibonacci_sequence[0] = 1
fibonacci_sequence[1] = 1
fun fibonacci(n):
i = 2;
while i <= n:
fibonacci_sequence[i] = fibonacci_sequence[i-2] + fibonacci_sequence[i-1]
return fibonacci_sequence[n]
In the above code, we started off with an empty list, then filled the results for 0th and 1st element in the Fibonacci sequence, and then kept filling the next element in the sequence by summing up the last two stored digits in the Fibonacci sequence list.
The key for dp is to find the variables to represent the states and deduce the transition function. For finding nth number in a Fibonacci sequence, the transition function is Fibonacci(n) = Fibonacci(n-2) + Fibonacci(n-1).