{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Dynamic Programming (DP)\n",
    "<a href=\"https://colab.research.google.com/github/rambasnet/FDSPython-Notebooks/blob/master/Ch21-DynamicProgramming.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>\n",
    "\n",
    "- https://www.cs.cmu.edu/~avrim/451f09/lectures/lect1001.pdf\n",
    "- https://www.geeksforgeeks.org/overlapping-subproblems-property-in-dynamic-programming-dp-1/\n",
    "- powerful technique that allows one to solve many different types of problemns in time $O(n^2)$ or $O(n^3)$ for which a naive approach would take exponential time\n",
    "- two main properties of a problem that warrents DP solution:\n",
    "    1. Overlapping Subproblems\n",
    "    2. Optimal Substructures"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Overlapping Subproblems\n",
    "- problem combines solutions from many overlapping sub-problems\n",
    "- DP is not useful when there are no common (overlapping) subproblems\n",
    "- computed solutions to sub-problems are stored in a look-up table to avoid recomputation\n",
    "- slighlty different from **Divide and Conquer** technqiue\n",
    "    - divide the problems into smaller non-overlapping subproblems and solve them independently\n",
    "    - e.g.: merge sort and quick sort\n",
    "\n",
    "## Optimal Substructures\n",
    "- optimal solution of the given problem can be obtained by using optimal solutions of its subproblems"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2 Types of DP solutions\n",
    "\n",
    "## 1. Top-Down (Memoization)\n",
    "- based on the Latin word memorandum, meaning \"to be remembered\" <img src=\"./resources/brain.jpg\" width=\"25%\" style=\"float:right\">\n",
    "- similar to word memorization, its a technique used in coding to improve program runtime by memorizing intermediate solutions\n",
    "- using dict type lookup data structure, one can memorize intermediate results of subproblems\n",
    "- tpically recursion use top-down approach\n",
    "\n",
    "### Process\n",
    "- start solving the given problem by breaking it down\n",
    "- first check to see if the given problem has been solved already\n",
    "    - if so, return the saved answer\n",
    "    - if not, solve it and save the answer\n",
    "    \n",
    "## 2. Bottom-Up (Tabulation)\n",
    "- start solving from the trivial subproblem\n",
    "- store the results in a table/list/array\n",
    "- move up towards the given problem by using the results of subproblems\n",
    "- typically iterative solutions uses bottom-up approach"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### simple recursive fib function\n",
    "- recall, fibonacci definition is recursive and has many common/overlapping subproblems\n",
    "<img src=\"resources/recursion-fib.svg\">"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "fib at 30th position = 1346269\n",
      "fib function count = 2692537\n"
     ]
    }
   ],
   "source": [
    "count = 0\n",
    "def fib(n):\n",
    "    global count\n",
    "    count += 1\n",
    "    if n <= 1:\n",
    "        return 1\n",
    "    f = fib(n-1) + fib(n-2)\n",
    "    return f\n",
    "\n",
    "n=30 #40, 50? takes a while\n",
    "print(\"fib at {}th position = {}\".format(n, fib(n)))\n",
    "print(\"fib function count = {}\".format(count))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### theoritical computational complexity\n",
    "- Time Complexity: $T(n)$ = time to calculate Fib(n-1) + Fib(n-2) + time to add them: O(1)\n",
    "- using Big-Oh (O) notation for upper-bound:\n",
    "    - $T(n) = T(n-1) + T(n-2) + O(1)$\n",
    "    - $T(n) = O(2^{n-1}) + O(2^{n-2}) + O(1)$\n",
    "    - $T(n) = O(2^n)$\n",
    "   \n",
    "    **precisely**\n",
    "    - $T(n) = O(1.6)^n$\n",
    "    \n",
    "        - 1.6... is called golden ratio - https://www.mathsisfun.com/numbers/golden-ratio.html\n",
    "- Space Complexity = $O(n)$ due to call stack"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.35596761399983734\n"
     ]
    }
   ],
   "source": [
    "#print(globals())\n",
    "import timeit\n",
    "print(timeit.timeit('fib(30)', number=1, globals=globals()))\n",
    "# big difference between 30 and 40"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### memoized recursive fib function"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "count = 0\n",
    "def MemoizedFib(memo, n):\n",
    "    global count\n",
    "    count += 1\n",
    "    if n <= 1:\n",
    "        return 1\n",
    "    if n in memo:\n",
    "        return memo[n]\n",
    "    memo[n] = MemoizedFib(memo, n-1) + MemoizedFib(memo, n-2)\n",
    "    return memo[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "fib at 1000th position = 70330367711422815821835254877183549770181269836358732742604905087154537118196933579742249494562611733487750449241765991088186363265450223647106012053374121273867339111198139373125598767690091902245245323403501\n",
      "fib function called 2118 times.\n"
     ]
    }
   ],
   "source": [
    "memo = {}\n",
    "n=1000 #try 40, 50, 60, 100, 500, 10000, ...\n",
    "print(\"fib at {}th position = {}\".format(n, MemoizedFib(memo, n)))\n",
    "print(\"fib function called {} times.\".format(count))   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.0009976609999284847\n"
     ]
    }
   ],
   "source": [
    "import timeit\n",
    "memo = {}\n",
    "n=1000\n",
    "print(timeit.timeit('MemoizedFib(memo, n)', number=1, globals=globals()))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### computational complexity of memoized fib\n",
    "- Time Complexity - $O(n)$\n",
    "- Space Complexity - $O(n)$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### normally large integer answers are reported in mod $(10^9+7)$\n",
    "- mod of a farily large prime number\n",
    "- need to know some modular arithmetic: https://www.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/modular-addition-and-subtraction\n",
    "- $(A+B) \\% C = (A \\% C + B \\% C) \\% C$\n",
    "- $(A-B) \\% C = (A \\% C - B \\% C) \\% C$\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "mod = 1000000007\n",
    "def MemoizedModFib(memo, n):\n",
    "    if n <= 1:\n",
    "        return 1\n",
    "    if n in memo:\n",
    "        return memo[n]\n",
    "    memo[n] = (MemoizedFib(memo, n-1)%mod + MemoizedFib(memo, n-2)%mod)%mod\n",
    "    return memo[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "fib at 1000th position = 107579939\n"
     ]
    }
   ],
   "source": [
    "memo = {}\n",
    "n=1000 #try 40, 50, 60, 100, 500, 10000, ...\n",
    "print(\"fib at {}th position = {}\".format(n, MemoizedModFib(memo, n))) "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### bottom-up (iterative) fibonacci solution\n",
    "- first calculate fib(0) then fib(1), then fib(2), fib(3), and so on"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [],
   "source": [
    "def iterativeFib(n):\n",
    "    # fib array/list\n",
    "    fib = [1]*(n+1) # initialize 0..n list with 1\n",
    "    for i in range(2, n+1):\n",
    "        fib[i] = fib[i-1] + fib[i-2]\n",
    "    return fib[i]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.0001866370002971962\n"
     ]
    }
   ],
   "source": [
    "n=1000\n",
    "print(timeit.timeit('iterativeFib(n)', number=1, globals=globals()))\n",
    "# is faster than recursive counterpart"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Coin Change Problem\n",
    "- https://www.geeksforgeeks.org/understanding-the-coin-change-problem-with-dynamic-programming/\n",
    "- essential to understanding the paradigm of DP\n",
    "- a variation of problem definition:\n",
    "    - Given a infinite number of coins of various denominations such as $1$ cent (penny), $5$ cents (nickel), and $10$ cents (dime), can you determine the total number of combinations (order doesn't matter) of the coins in the given list to make up some amount $N$?\n",
    "- Example 1: \n",
    "    - Input: coins = $[1, 5, 10]$, $N = 8$\n",
    "    - Output: 2\n",
    "    - Combinations: \n",
    "        1. $1 + 1 + 1 + 1+1+1+1+1 = 8$\n",
    "        - $1 + 1 + 1 + 5 = 8 $  \n",
    "- Example 2:\n",
    "    - Input: coins = $[1, 5, 10], N = 10$\n",
    "    - Output: 4\n",
    "    - Combinations:\n",
    "        1. $1+1+1+1+1+1+1+1+1+1=10$\n",
    "        - $ 1+1+1+1+1+5 = 10$\n",
    "        - $ 5+5 = 10$\n",
    "        - $10 = 10$\n",
    "- Implementation:\n",
    "    - we use tabulation/list/array to store the number of ways for outcome $N = 0$ to $12$\n",
    "    - values of list represent the number of ways; indices represent the outcome/sum $N$\n",
    "    - so ways = [0, 0, 0, 0, 0, 0....] initialized with 12 0s\n",
    "    - base case:\n",
    "        - ways[0] = 1; there's 1 way to make sum N=0 using 0 coin\n",
    "    - for each coin:\n",
    "        - if the value of coin is less than the outcome/index $N$,\n",
    "            - update the ways[n] = ways[n-coin] + ways[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {},
   "outputs": [],
   "source": [
    "def countWays(coins, N):\n",
    "    # use ways table to store the results\n",
    "    # ways[i] will store the number of solutions for value i\n",
    "    ways = [0]*(N+1) # initialize all values 0-12 as 0\n",
    "    # base case \n",
    "    ways[0] = 1\n",
    "    # pick all coins one by one\n",
    "    # update the ways starting from the value of the picked coin\n",
    "    print('values:', list(range(N+1)))\n",
    "    for coin in coins:\n",
    "        for i in range(coin, N+1):\n",
    "            ways[i] += ways[i-coin]\n",
    "        print('ways:  ', ways, coin)\n",
    "    return ways[N]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "values: [0, 1, 2, 3, 4, 5, 6, 7, 8]\n",
      "ways:   [1, 1, 1, 1, 1, 1, 1, 1, 1] 1\n",
      "ways:   [1, 1, 1, 1, 1, 2, 2, 2, 2] 5\n",
      "ways:   [1, 1, 1, 1, 1, 2, 2, 2, 2] 10\n",
      "Number of Ways to get 8 = 2\n"
     ]
    }
   ],
   "source": [
    "coins = [1, 5, 10]\n",
    "N = 8\n",
    "print('Number of Ways to get {} = {}'.format(N, countWays(coins, N)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "values: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]\n",
      "ways:   [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] 1\n",
      "ways:   [1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 3] 5\n",
      "ways:   [1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 4] 10\n",
      "Number of Ways to get 10 = 4\n"
     ]
    }
   ],
   "source": [
    "N = 10\n",
    "print('Number of Ways to get {} = {}'.format(N, countWays(coins, N)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "values: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]\n",
      "ways:   [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] 1\n",
      "ways:   [1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3] 5\n",
      "ways:   [1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 4, 4, 4] 10\n",
      "Number of Ways to get 10 = 4\n"
     ]
    }
   ],
   "source": [
    "N = 10\n",
    "print('Number of Ways to get {} = {}'.format(N, countWays(coins, 12)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## find minimum number of coins that make a given value/change\n",
    "- Problem: \n",
    "    - Input: $coins = [5, 10, 25], N = 30$\n",
    "    - Output: 2\n",
    "    - Combinations: $25 + 5 = 30$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {},
   "outputs": [],
   "source": [
    "import math\n",
    "\n",
    "# DP solution for min coin count to make the change N\n",
    "def minCoins(coins, N):\n",
    "    # count list stores the minimum number of coins required for i value\n",
    "    # all values 0-N are initialized to infinity\n",
    "    count = [math.inf]*(N+1)\n",
    "    # base case\n",
    "    # no. of coin required to make 0 value is 0\n",
    "    count[0] = 0\n",
    "    # computer min coins for all values from 1 to N\n",
    "    for i in range(1, N+1):\n",
    "        for coin in coins:\n",
    "            # for every coin smaller than value i\n",
    "            if coin <= i:\n",
    "                if count[i-coin]+1 < count[i]:\n",
    "                    count[i] = count[i-coin]+1\n",
    "    return count[N]\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "min coins required to give total of 6 change = 2\n"
     ]
    }
   ],
   "source": [
    "coins = [1, 3, 4]\n",
    "N = 6\n",
    "print('min coins required to give total of {} change = {}'.format(N, minCoins(coins, N)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Exercises\n",
    "1. Ocean's Anti-11 - https://open.kattis.com/problems/anti11\n",
    "    - Hint: count all possible n length binary integers (without 11) for the first few (2,3,4) positive integers and you'll see a Fibonaccii like pattern that gives the total number of possible binaries without 11 in them\n",
    "- Write a program that finds factorials of a bunch of positive integer numbers. Would memoization improve time complexity of the program? "
   ]
  },
  {
   "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.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}