Fibonacci
Code
public static void main(String[] args) {
System.out.println(fib(30));
System.out.println(fibonacci(30));
}
//recursion
public static int fib(int n) {
if(n < 2) return n;
int prev = 0, cur = 1;
for (int i = 2; i <= n; i++) {
int sum = prev + cur;
prev = cur;
cur = sum;
}
return cur;
}
public static int fibonacci(int n) {
int dp[] = new int[n + 1];
return fibonacci(dp, n);
}
private static int fibonacci(int[] dp, int n) {
if(n < 2) return n;
dp[n] = fibonacci(dp, n - 1) + fibonacci(dp, n - 2);
return dp[n];
}