      "collapsed": false
     },
     "outputs": [],
     "source": [
      "num_items = 10\n",
      "cache = [None] * (num_items + 1)\n",
      "\n",
      "\n",
      "def fib_dynamic(n):\n",
      "    if n == 0 or n == 1:\n",
      "        return n\n",
      "    if cache[n] != None:\n",
      "        return cache[n]\n",
      "    cache[n] = fib_dynamic(n-1) + fib_dynamic(n-2)\n",
      "    return cache[n]"
     ]
    },
    {
     "cell_type": "code",
     "execution_count": 3,
 
</s> remove     "def fib_iterative(n):\n",
    "    a = 0\n",
    "    b = 1\n",
    "    for _ in range(n):\n",
    "        a, b = b, a + b\n",
    "    return a"
 </s> add     "def fib_dynamic(n):\n",
    "    cache = {}\n",
    "    return _fib_dynamic(n, cache)\n",
    "\n",
    "\n",
    "def _fib_dynamic(n, cache):\n",
    "    if n == 0 or n == 1:\n",
    "        return n\n",
    "    if n in cache:\n",
    "        return cache[n]\n",
    "    cache[n] = _fib_dynamic(n-1, cache) + _fib_dynamic(n-2, cache)\n",
    "    return cache[n]" </s> remove     "num_items = 10\n",
    "cache = [None] * (num_items + 1)\n",
    "\n",
    "\n",
    "def fib_dynamic(n):\n",
 </s> add     "def fib_iterative(n):\n", </s> remove     "def fib_iterative(n):\n",
 </s> add     "def fib_dynamic(n):\n", </s> remove     "* None"
 </s> add     "* Does the sequence start at 0 or 1?\n",
    "    * 0\n",
    "* Can we assume the inputs are valid non-negative ints?\n",
    "    * Yes\n",
    "* Are you looking for a recursive or iterative solution?\n",
    "    * Either\n",
    "* Can we assume this fits memory?\n",
    "    * Yes" </s> remove     "* None"
 </s> add     "* Does the sequence start at 0 or 1?\n",
    "    * 0\n",
    "* Can we assume the inputs are valid non-negative ints?\n",
    "    * Yes\n",
    "* Are you looking for a recursive or iterative solution?\n",
    "    * Implement both\n",
    "* Can we assume this fits memory?\n",
    "    * Yes"
    "def fib_iterative(n):\n",
    "    a = 0\n",
    "    b = 1\n",
    "    for _ in range(n):\n",
    "        a, b = b, a + b\n",
    "    return a"
      "collapsed": false
     },
     "outputs": [],
     "source": [
    "def fib_iterative(n):\n",
    "    a = 0\n",
    "    b = 1\n",
    "    for _ in range(n):\n",
    "        a, b = b, a + b\n",
    "    return a"
    "def fib_iterative(n):\n",
    "    a = 0\n",
    "    b = 1\n",
    "    for _ in range(n):\n",
    "        a, b = b, a + b\n",
    "    return a"
    "def fib_iterative(n):\n",
    "    a = 0\n",
    "    b = 1\n",
    "    for _ in range(n):\n",
    "        a, b = b, a + b\n",
    "    return a"
    "def fib_iterative(n):\n",
    "    a = 0\n",
    "    b = 1\n",
    "    for _ in range(n):\n",
    "        a, b = b, a + b\n",
    "    return a"
    "def fib_iterative(n):\n",
    "    a = 0\n",
    "    b = 1\n",
    "    for _ in range(n):\n",
    "        a, b = b, a + b\n",
    "    return a"
    "def fib_iterative(n):\n",
    "    a = 0\n",
    "    b = 1\n",
    "    for _ in range(n):\n",
    "        a, b = b, a + b\n",
    "    return a"
    "def fib_iterative(n):\n",
    "    a = 0\n",
    "    b = 1\n",
    "    for _ in range(n):\n",
    "        a, b = b, a + b\n",
    "    return a"
    "def fib_iterative(n):\n",
    "    a = 0\n",
    "    b = 1\n",
    "    for _ in range(n):\n",
    "        a, b = b, a + b\n",
    "    return a"
    "def fib_iterative(n):\n",
    "    a = 0\n",
    "    b = 1\n",
    "    for _ in range(n):\n",
    "        a, b = b, a + b\n",
    "    return a"
    "def fib_iterative(n):\n",
    "    a = 0\n",
    "    b = 1\n",
    "    for _ in range(n):\n",
    "        a, b = b, a + b\n",
    "    return a"
    "def fib_iterative(n):\n",
    "    a = 0\n",
    "    b = 1\n",
    "    for _ in range(n):\n",
    "        a, b = b, a + b\n",
    "    return a"
     ]
    },
    {
     "cell_type": "code",
     "execution_count": 3,
keep keep keep keep replace replace replace replace replace replace replace replace replace replace replace keep keep keep keep keep
 Polish fibonacci challenge and solution (#91)

Update constraints, test cases, tests, and code. 
recursion_dynamic/fibonacci/fibonacci_solution.ipynb