Tag Archives: dynamic-programming

Project Euler - Problem 14

Here is one again a very intricate problem from Project Euler. It has no solution sheet as oppose to the other problems at the site. Therefore there is no consensus on the best solution.

Below is the problem: (I really suggest you to observe some of the example sequences. It has really interesting behaviours. 🙂 )

The following iterative sequence is defined for the set of positive integers:

n → n/2 (n is even)
n → 3n + 1 (n is odd)

Using the rule above and starting with 13, we generate the following sequence: Continue reading Project Euler - Problem 14

Share

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