Bottom Up Approach

Bottom-Up Approach in Dynamic Programming :

Start from the bottom then rise to the top. Thats means start computing result for the subproblem. 

Using the subproblem result solve another subproblem and finally solve the whole problem.

Let's find the nth member of a Fibonacci series.

Fibonacci(0) = 0

Fibonacci(1) = 1

Fibonacci(2) = Fibonacci(0) + Fibonacci(1)

Fibonacci(3) = Fibonacci(1) + Fibonacci(2)

We can solve the problem step by step :

1. Find 0th member

2. Find 1st member

3. Calculate the 2nd member using 0th and 1st member

4. Calculate the 3rd member using 1st and 2nd member

5. By doing this we can easily find the nth member.

Code are Given Below ::

#include<bits/stdc++.h>

using namespace std;

int fibonacci(int n)

{

int fib[n+1];

fib[0] = 0;

fib[1] = 1;

for(int i=2;i<=n;i++)

fib[i] = fib[i-1] + fib[i-2];

return fib[n];

}

int main()

{

int n;

cout << "Enter A Number :: ";

cin >> n;

cout << "\n";

cout << "nth Fibonacci Number is :: ";

cout << fibonacci(n) << "\n";

return 0;

}

Problem :

1. https://codeforces.com/problemset/problem/189/A

Solution : https://codeforces.com/contest/189/submission/106743986