Dynamic programming for fibonacci

main.dart

void main() {
  int i = 150;

  final fib = fibonacciWithDynamicProgramming();
  print('fibonacciWithDynamicProgramming($i) = ${fib(i)}');

  print('fibonacci($i) = ${fibonacci(i)}'); //Uncomment this to try large numbers
}

/// Computes the nth Fibonacci number.
int fibonacci(int n) {
  return n < 2 ? n : (fibonacci(n - 1) + fibonacci(n - 2));
}

/// Computes the nth Fibonacci number with cache.
Function fibonacciWithDynamicProgramming() {
  var cache = <int, dynamic>{};

  int fibonacci(int n) {
    if (cache.containsKey(n)) {
      return cache[n];
    } else if (n < 2) {
      return n;
    } else {
      cache[n] = (fibonacci(n - 1) + fibonacci(n - 2));
      return cache[n];
    }
  }

  return fibonacci;
}