Naive recursion

int fib(int n) {
  if (n < 2) return n;
  return fib(n-1) + fib(n-2);
}
// Time: O(2^N). Try fib(45).
Advertisement

Memoized

Map memo = new HashMap<>();
int fib(int n) {
  if (n < 2) return n;
  if (memo.containsKey(n)) return memo.get(n);
  int r = fib(n-1) + fib(n-2);
  memo.put(n, r);
  return r;
}
// Time: O(N). Space: O(N).
Advertisement

Bottom-up tabulation

int fib(int n) {
  int[] dp = new int[n + 1];
  dp[0] = 0; dp[1] = 1;
  for (int i = 2; i <= n; i++) dp[i] = dp[i-1] + dp[i-2];
  return dp[n];
}

Space-optimized

int fib(int n) {
  int a = 0, b = 1;
  for (int i = 2; i <= n; i++) { int c = a + b; a = b; b = c; }
  return n == 0 ? a : b;
}
// Space: O(1). Time: O(N).

The lesson

Every DP problem you might solve top-down or bottom-up. Both work. Space-optimize by keeping only what transition needs.

Naive recursion

int fib(int n) {
  if (n < 2) return n;
  return fib(n-1) + fib(n-2);
}
// Time: O(2^N). Try fib(45).

Memoized

Map memo = new HashMap<>();
int fib(int n) {
  if (n < 2) return n;
  if (memo.containsKey(n)) return memo.get(n);
  int r = fib(n-1) + fib(n-2);
  memo.put(n, r);
  return r;
}
// Time: O(N). Space: O(N).

Bottom-up tabulation

int fib(int n) {
  int[] dp = new int[n + 1];
  dp[0] = 0; dp[1] = 1;
  for (int i = 2; i <= n; i++) dp[i] = dp[i-1] + dp[i-2];
  return dp[n];
}

Space-optimized

int fib(int n) {
  int a = 0, b = 1;
  for (int i = 2; i <= n; i++) { int c = a + b; a = b; b = c; }
  return n == 0 ? a : b;
}
// Space: O(1). Time: O(N).