C#•5mo ago

✅ Fibonacci sequence

Im trying to learn dynamic programming and im struggling to understand the bottom up approach for the fibonacci sequence problem. I watched a couple of videos on this topic but all of the code in them is written in other languages. It would be great if someone wrote the method in c# so i could understand it better. Thank you in advance!

12 Replies

MODiX•5mo ago

blueberriesiftheywerecats

REPL Result: Success

Console.WriteLine(fib(8 + 1));

int fib(int n)
{
    var t = new List<int> { 0, 1 };
    for (int i = 2; i < n; i++)
        t.Add(t[i - 1] + t[i - 2]);
    return t[n - 1];
}

Console.WriteLine(fib(8 + 1));

int fib(int n)
{
    var t = new List<int> { 0, 1 };
    for (int i = 2; i < n; i++)
        t.Add(t[i - 1] + t[i - 2]);
    return t[n - 1];
}

Console Output

Compile: 389.877ms | Execution: 86.404ms | React with ❌ to remove this embed.

Moods•5mo ago

while the first code snippet is right(and even sorta optimal)...that's a pretty bad way to explain the point of memoization Memoization exists for situations where there is redundant calculations being done. for example here,

public int Fib(int nth_number)
{
     if(nth_number == 0) return 0;
     if(nt_number == 1) return 1;

     return Fib(nth_number - 1) + Fib(nth_number - 2); 
}

public int Fib(int nth_number)
{
     if(nth_number == 0) return 0;
     if(nt_number == 1) return 1;

     return Fib(nth_number - 1) + Fib(nth_number - 2); 
}

If i used nth_number as something like 5, it'd start off as a call to Fib(5), then Fib(5) calls (case a)Fib(4) and Fib(3) for case a: Fib(4) calls Fib(3) and Fib(2) Fib(3) calls Fib(2) and Fib(1), then Fib(2) calls Fib(1) and Fib(0) --ends here Fib(2) (from the Fib(4) call) is done again (an example of a redundant call as Fib(2) was already done) for something like Fibonacci it wouldn't matter too much to have redundant calls, but for situations similar in nature to it with stuff like expensive calculations in each function call, it pays to have redundant calls. That's where memoization comes in, it caches(stores) each call once completed so that if this call were to happen again it would not need to do the expensive calculations again, it just returns the cached call. A way to properly implement memoization in Fibonacci would be

public int Fib(int nth_number)
{
     //all the elements in the array are 0
     int[] memo = new int[nth_number];
     memo[0] = 0;                       //first number is always zero
     memo[1] = 1;                       //second number is always one

     //im assuming nth_number is never negative
     if(nth_number < 2) return memo[nth_number];
     
     return Helper(nth_number, memo):
}

private int Helper(int n, int[] memo)
{    
     if(memo[n] != 0) return memo[n];
     else{
         memo[n] = Helper(n - 1, memo) + Helper(n - 2, memo);
         return memo[n];
     }    
}

public int Fib(int nth_number)
{
     //all the elements in the array are 0
     int[] memo = new int[nth_number];
     memo[0] = 0;                       //first number is always zero
     memo[1] = 1;                       //second number is always one

     //im assuming nth_number is never negative
     if(nth_number < 2) return memo[nth_number];
     
     return Helper(nth_number, memo):
}

private int Helper(int n, int[] memo)
{    
     if(memo[n] != 0) return memo[n];
     else{
         memo[n] = Helper(n - 1, memo) + Helper(n - 2, memo);
         return memo[n];
     }    
}

i think this is also top-down approach...i am not 100% sure but that should be the term, for bottom-up approach instead of doing recusively + using caching you'd just do it completely iteratively like with a loop

public int FibButBottomUp(int nth_number)
{
     if(nth_number == 0) return 0;
     if(nth_number == 1) return 1;


     int first_num = 0, second_num = 1;
     int count = 2;

     while(count < nth_number)
     {
          int temp = first_num + second_num; //getting the next number
          first_num = second_num;        
          second_num = temp;

          count++;
     }

     return second_num;
}

public int FibButBottomUp(int nth_number)
{
     if(nth_number == 0) return 0;
     if(nth_number == 1) return 1;


     int first_num = 0, second_num = 1;
     int count = 2;

     while(count < nth_number)
     {
          int temp = first_num + second_num; //getting the next number
          first_num = second_num;        
          second_num = temp;

          count++;
     }

     return second_num;
}

it may be <= instead of < but i am not on vscode and im too stupid to do it in my head okay it is < that's how it is done bottom-up

vl4doOP•5mo ago

THANK YOU! im gonna read everything and see if i understand it all

vl4doOP•5mo ago

isnt this topdown approach better? the dictionary is outside of the methods so it stores the values even if the method is called again

vl4doOP•5mo ago

i used that instead of the declaring the dict in the method because i was testing it like this:

Moods•5mo ago

yeah i could have made the array outside the method and put it as a class field. That is actually my preferred way to do stuff like this cus it makes it clearer for me

vl4doOP•5mo ago

also, do you think the fib sequence is 0 1 1 2.. or 0 1 2 ? or something else 1 1 2..

Moods•5mo ago

it's 0, 1 as the first two numbers then it starts next number 0 + 1 and continue

vl4doOP•5mo ago

right this is supposed to be n<=3 btw, this is supposed to be n<=3 btw and here why not use a for loop instead of while and count variable

Moods•5mo ago

oh actually yeah why didn't i great question, a for-loop is better i just did NOT think of it

vl4doOP•5mo ago

ok well thank you you helped a lot if i close this thread will this it be deleted?

Moods•5mo ago

honestly I'm not sure

Gaming

Programming

✅ Fibonacci sequence