The Modified Fibonacci Sequence Problem
I recently got into Dynamic Programming. I started my journey first by watching some youtube videos, and then slowly moved into reading content, and then finally by solving problems.
Most programmers have faced the Fibonacci sequence problems. Its the idea of calculating the next value in a sequence by adding the previous two values in the sequence.
t2 = t1 + t0;You can use two approaches to solve this problem: iterative, or recursive.
Many people have trouble solving this problem recursively. I did too. Then I spent several hours and days figuring out recursive structures and methods. Its still not entirely clear to me, but I’m starting to finally get the hang of it.
Below, I am going to provide two solutions to a modified Fibonacci Sequence problem, one that was easy for me to write, and one that took much longer.
t2 = t0 + t1^2;// Here we are going to find the next value in the sequence by taking the sum of the previous' element's value squared and the value of the element two elements back
Iteration Method:
The idea here is to compute the n’th Fibonacci value given the first and second term in the sequence. In the following solution, Im expecting very large numbers to be part of the solution, so I do a little practice with the BigInteger class provided from System.Numerics namespace.

The variable val representations the n’th sequence value. Because my iteration is zero-based, I need to subtract one so I dont calculate too far. I additionally subtract another one because I calculate the final answer in advance. The calculation happens before I update first and second.
This solution can be better, however, it works, and fits our needs.
Recursion and Dynamic Programming:
This code is actually much simper to read, but it is much harder to understand, at least at first. In all dynamic programming problems, you have to declare your base cases for the recursion to stop, and for your stack to collapse.
So in the following solution, I pass my base cases to every single iteration of the method. Im not using any memoization, because I completely forgot about it until now.

It took me much longer to think (and also to test) about this solution, even though it seems like there is not that much code here.
Even though we arent using that much space here to calculate our sequence values, we are at O(2^n) time complexity. Its pretty scary once you start calculating large sequences. Memoizations helps mediate this problem, and sub-problems.
Welcome to Dynamic Programming !
