Nov 8, 2018

Dynamic Programming

Dynamic programming is a technique for solving problems with the following properties:
  1. An instance is solved using the solutions for smaller instances.
  2. The solution for a smaller instance might be needed multiple times.
  3. The solutions to smaller instances are stored in a table, so that each smaller instance is solved only once.
  4. Additional space is used to save time.
This example perfectly fit those 4 properties. Therefore, it can be solve by using dynamic programming.
public static int[] A = new int[100];
public static int f3(int n) {
 if (n <= 2)
  A[n]= n;
 if(A[n] > 0)
  return A[n];
  A[n] = f3(n-1) + f3(n-2);
//store results so we only need to calculate once
 return A[n];