Tag Archives: fibonacci

Dynamic Programming Example - Find n.th Fibonacci number -

Dynamic programming is a concept that provides faster solutions for divide and conquer problems that have some number of overlapping sub problems. Generally this concept is used for optimization problems like finding longest common sub-sequence of two arrays.

However I used the concept in finding n th Fibonacci number. Here is the code that I used.

public class Main {
	int q;
	public static void main(String args[]){
		new Main().fibonacci(40);
	}

	public void fibonacci(int n){
		ArrayList r = new ArrayList();

		for(int i = 0; i < n+1; i++){
			r.add(-1);
		}
		fibonacci(n, r);
		System.out.println(q);
	}

	public int fibonacci(int n, ArrayList r){
		if (r.get(n)>= 0){
			return r.get(n);
		}else if(n == 0){
			q = 0;
		}else if(n == 1){
			q = 1;
		}else{
			q = fibonacci(n-1, r)+fibonacci(n-2, r);
		}
		r.set(n, q);
		return q;
	}
}
Share