Fibonacci Using DP in DSA C - Build from Scratch

Fibonacci Using DP

📖 Scenario: You want to find the nth number in the Fibonacci sequence quickly. The Fibonacci sequence starts with 0 and 1, and each next number is the sum of the two before it.Using a smart way called Dynamic Programming (DP), you will store results of smaller problems to avoid repeating work.

🎯 Goal: Build a program that calculates the nth Fibonacci number using Dynamic Programming with an array to store intermediate results.

📋 What You'll Learn

Create an integer variable n with value 10

Create an integer array fib of size n + 1

Initialize the first two Fibonacci numbers in fib[0] and fib[1]

Use a for loop with variable i from 2 to n to fill the fib array

Print the nth Fibonacci number stored in fib[n]

💡 Why This Matters

🌍 Real World

Calculating Fibonacci numbers efficiently is useful in computer graphics, financial models, and algorithm design where repeated calculations happen.

💼 Career

Understanding Dynamic Programming and memoization is key for software engineering roles, especially in optimization and algorithm design.

1

Create the input variable and array

Create an integer variable called n and set it to 10. Then create an integer array called fib with size n + 1.

DSA C

int n = 10;
int fib[11];
// Your code here

Hint

Remember, the array size should be n + 1 to hold Fibonacci numbers from 0 to n.

2

Initialize the first two Fibonacci numbers

Set fib[0] to 0 and fib[1] to 1 to start the Fibonacci sequence.

DSA C

int n = 10;
int fib[11];
fib[0] = 0;
fib[1] = 1;
// Your code here

Hint

The first two Fibonacci numbers are always 0 and 1.

3

Fill the Fibonacci array using a loop

Use a for loop with variable i starting from 2 up to and including n. Inside the loop, set fib[i] to the sum of fib[i - 1] and fib[i - 2].

DSA C

int n = 10;
int fib[11];
fib[0] = 0;
fib[1] = 1;
for (int i = 2; i <= n; i++) {
    // Your code here
}

Hint

Each Fibonacci number is the sum of the two before it.

4

Print the nth Fibonacci number

Print the value stored in fib[n] using printf.

DSA C

int n = 10;
int fib[11];
fib[0] = 0;
fib[1] = 1;
for (int i = 2; i <= n; i++) {
    fib[i] = fib[i - 1] + fib[i - 2];
}
// Your code here

Hint

The 10th Fibonacci number is 55.