{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Memoization\n",
    "\n",
    "In this lecture we will discuss memoization and dynamic programming. For your homework assignment, read the [Wikipedia article on Memoization](https://en.wikipedia.org/wiki/Memoization), before continuing on with this lecture!\n",
    "\n",
    "____\n",
    "\n",
    "Memoization effectively refers to remembering (\"memoization\" -> \"memorandum\" -> to be remembered) results of method calls based on the method inputs and then returning the remembered result rather than computing the result again. You can think of it as a cache for method results. We'll use this in some of the interview problems as improved versions of a purely recursive solution.\n",
    "\n",
    "A simple example for computing factorials using memoization in Python would be something like this:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Create cache for known results\n",
    "factorial_memo = {}\n",
    "\n",
    "def factorial(k):\n",
    "    \n",
    "    if k < 2: \n",
    "        return 1\n",
    "    \n",
    "    if not k in factorial_memo:\n",
    "        factorial_memo[k] = k * factorial(k-1)\n",
    "        \n",
    "    return factorial_memo[k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "24"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "factorial(4)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Note how we are now using a dictionary to store previous results of the factorial function! We are now able to increase the efficiency of this function by remembering old results!\n",
    "\n",
    "Keep this in mind when working on the Coin Change Problem and the Fibonacci Sequence Problem.\n",
    "\n",
    "___\n",
    "\n",
    "We can also encapsulate the memoization process into a class:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Memoize:\n",
    "    def __init__(self, f):\n",
    "        self.f = f\n",
    "        self.memo = {}\n",
    "    def __call__(self, *args):\n",
    "        if not args in self.memo:\n",
    "            self.memo[args] = self.f(*args)\n",
    "        return self.memo[args]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Then all we would have to do is:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def factorial(k):\n",
    "    \n",
    "    if k < 2: \n",
    "        return 1\n",
    "    \n",
    "    return k * factorial(k - 1)\n",
    "\n",
    "factorial = Memoize(factorial)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Try comparing the run times of the memoization versions of functions versus the normal recursive solutions!"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}