Dynamic Programming.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "this is using closure function \n",
      "fibonacci using DP\n",
      "55\n"
     ]
    }
   ],
   "source": [
    "def fibonacciMaster():\n",
    "    \"\"\"this is using closure function \"\"\"\n",
    "    cache = dict()\n",
    "    def fib(n):\n",
    "        \"\"\"fibonacci using DP\"\"\"\n",
    "        if n in cache:\n",
    "            return cache[n]\n",
    "        else:\n",
    "            if n < 2:\n",
    "                return n\n",
    "            else:\n",
    "                cache[n] = fib(n-1) + fib(n-2)\n",
    "#                 print(cache)\n",
    "                return cache[n]\n",
    "    return fib\n",
    "print(fibonacciMaster.__doc__)\n",
    "fibFaster = fibonacciMaster()\n",
    "print(fib.__doc__)\n",
    "print(fibFaster(10))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "fibonacci using DP -> with bottom up approach > which avoids recursion\n",
      "55\n"
     ]
    }
   ],
   "source": [
    "def fibonacciMaster2(n):\n",
    "    \"\"\"fibonacci using DP -> with bottom up approach > which avoids recursion\"\"\"\n",
    "    answer = [0,1];\n",
    "    for i in range(2,n+1):\n",
    "        answer.append(answer[i-2]+answer[i-1])\n",
    "    return answer.pop(-1)\n",
    "\n",
    "print(fibonacciMaster2.__doc__)\n",
    "print(fibonacciMaster2(10))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Given a number N, print the first N fibonacci numbers using DP -> with bottom up approach > which avoids recursion\n",
      "[1, 1, 2, 3, 5, 8, 13]\n"
     ]
    }
   ],
   "source": [
    "\"\"\"\n",
    "Q url -> https://practice.geeksforgeeks.org/problems/print-first-n-fibonacci-numbers/0\n",
    "\n",
    "Given a number N, print the first N fibonacci numbers.\n",
    "\n",
    "Input:\n",
    "The first line of input contains an integer T denoting the number of test cases. Then T test cases follow. The first line of each test case contains the integer N.\n",
    "\n",
    "Output:\n",
    "Print the first n fibonacci numbers with a space between each number. Print the answer for each test case in a new line.\n",
    "\n",
    "Constraints:\n",
    "1<= T <=100\n",
    "1<= N <=84\n",
    "\n",
    "Example:\n",
    "Input:\n",
    "2\n",
    "7\n",
    "5\n",
    "\n",
    "Output:\n",
    "1 1 2 3 5 8 13\n",
    "1 1 2 3 5\n",
    "\"\"\"\n",
    "\n",
    "def firstNfibonaccinumbers(n):\n",
    "    \"\"\"Given a number N, print the first N fibonacci numbers using DP -> with bottom up approach > which avoids recursion\"\"\"\n",
    "    answer = [0,1];\n",
    "    for i in range(2,n+1):\n",
    "        answer.append(answer[i-2]+answer[i-1])\n",
    "    return answer[1:]\n",
    "\n",
    "print(firstNfibonaccinumbers.__doc__)\n",
    "print(firstNfibonaccinumbers(7))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}