Lesson 04 - Dynamic Programming.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "tags": []
   },
   "source": [
    "## Dynamic programming\n",
    "\n",
    "Dynamic programming can be thought of as an optimization on top of a recursive problem, where we cache intermediate results in a 'dynamic' array. This can be done either bottom-up or top-down (aka memoization). The important thing to understand is that bottom-up and top-down are equivalent, they're just different styles of arriving at the same solution, where bottom-up is arguably more elegant."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem: the Fibonaccy sequence\n",
    "\n",
    "The Fibonacci sequence is:  \n",
    "fib(0) = 0  \n",
    "fib(1) = 1  \n",
    "fib(n>1) = fib(n-1) - fib(n-2)  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "def fib_slow(n):\n",
    "\n",
    "    # this recursive algorithm scales like 2^n - which is terrible!\n",
    "    if n==0 or n==1:\n",
    "        return n\n",
    "    else: \n",
    "        return fib_slow(n-2) + fib_slow(n-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 297 ms, sys: 2.67 ms, total: 300 ms\n",
      "Wall time: 299 ms\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "832040"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%%time\n",
    "\n",
    "# note how slow this is\n",
    "fib_slow(30)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "def fib_bu(n):\n",
    "    # bottom-up approach. solve the smaller numbers first, and go higher incrementally\n",
    "    if n==0 or n==1:\n",
    "        return n\n",
    "    a,b = 0,1\n",
    "    i = 2\n",
    "    while i<n:\n",
    "        a,b = b,a+b\n",
    "        i += 1\n",
    "    return a+b"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 23 µs, sys: 1e+03 ns, total: 24 µs\n",
      "Wall time: 31 µs\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "832040"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%%time\n",
    "\n",
    "# note how much faster this is\n",
    "fib_bu(30)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "def fib_memo(n):\n",
    "    # in the memoization approach, we use a cache to store values we already computed previously\n",
    "    cache = {}\n",
    "    def find_fib(n, cache):\n",
    "        if n==0 or n==1:\n",
    "            return n\n",
    "        elif n in cache.keys():\n",
    "            return cache[n]\n",
    "        else:\n",
    "            res = find_fib(n-2,cache) + find_fib(n-1,cache)\n",
    "            cache[n] = res\n",
    "        return res\n",
    "    return find_fib(n, cache)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 73 µs, sys: 1e+03 ns, total: 74 µs\n",
      "Wall time: 79.2 µs\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "832040"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%%time\n",
    "\n",
    "# similarly fast as bottom-up approach\n",
    "fib_memo(30)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "tags": []
   },
   "source": [
    "## Problem: coin chance\n",
    "\n",
    "Given coins c, what's the minimum number of coins needed to make amount 'target'?\n",
    "\n",
    "First, note the mathematical property of the solution, aka the induction rule:\n",
    "\n",
    "F(x) = min( 1 + F(x-c) ) \n",
    "\n",
    "where the min is taken over all c<=x.\n",
    "\n",
    "Once we have the induction rule, the rest of the code is really straightforwards:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "def coin_change(target,coins):\n",
    "\n",
    "    dp = [0] + [np.infty]*target\n",
    "    for x in range(1,target+1):\n",
    "        candidates = [1+dp[x-c] for c in coins if x-c>=0]\n",
    "        if len(candidates)>0:\n",
    "            dp[x] = min(candidates)\n",
    "        \n",
    "        else:\n",
    "            # we can't make x with coins at all!\n",
    "            dp[x] = -1\n",
    "        print(dp)  # for illustration purposes\n",
    "            \n",
    "    return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0, 1, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf]\n",
      "[0, 1, 2, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf]\n",
      "[0, 1, 2, 1, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf]\n",
      "[0, 1, 2, 1, 2, inf, inf, inf, inf, inf, inf, inf, inf, inf]\n",
      "[0, 1, 2, 1, 2, 3, inf, inf, inf, inf, inf, inf, inf, inf]\n",
      "[0, 1, 2, 1, 2, 3, 2, inf, inf, inf, inf, inf, inf, inf]\n",
      "[0, 1, 2, 1, 2, 3, 2, 1, inf, inf, inf, inf, inf, inf]\n",
      "[0, 1, 2, 1, 2, 3, 2, 1, 2, inf, inf, inf, inf, inf]\n",
      "[0, 1, 2, 1, 2, 3, 2, 1, 2, 3, inf, inf, inf, inf]\n",
      "[0, 1, 2, 1, 2, 3, 2, 1, 2, 3, 2, inf, inf, inf]\n",
      "[0, 1, 2, 1, 2, 3, 2, 1, 2, 3, 2, 3, inf, inf]\n",
      "[0, 1, 2, 1, 2, 3, 2, 1, 2, 3, 2, 3, 4, inf]\n",
      "[0, 1, 2, 1, 2, 3, 2, 1, 2, 3, 2, 3, 4, 3]\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "coin_change(13, [1,3,7])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "from functools import lru_cache\n",
    "def coin_change_memo(coins,target):\n",
    "\t\n",
    "\t@lru_cache\n",
    "\tdef _coinchange(x):\n",
    "\t\tif x==0:\n",
    "\t\t\treturn 0\n",
    "\t\telse:\n",
    "\t\t\tcandidates = [1+_coinchange(x-c) for c in coins if x-c>=0]\n",
    "\t\t\treturn min(candidates if candidates else -1)\n",
    "\n",
    "\treturn _coinchange(target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "coin_change_memo([1,3,7],13)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem: length of the longest increasing sub-sequence\n",
    "\n",
    "Example: [1,3,2,5,6,4] --> 1,2,5,6 --> 4\n",
    "\n",
    "Again let's start with the induction rule. Suppose we know dp[j], the lenght of LIS at position j, then what's the result dp[i] for i>j?\n",
    "\n",
    "Answer: dp[i] = max(dp[i], 1+dp[j]) if nums[i]>nums[j] \n",
    "\n",
    "And there we have it. Code:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [],
   "source": [
    "def lis(nums):\n",
    "    dp = [1]*len(nums)\n",
    "    for i in range(1,len(nums)):\n",
    "        for j in range(0,i):\n",
    "            if nums[i]>nums[j]:\n",
    "                dp[i] = max(dp[i],1+dp[j])\n",
    "        print(dp)\n",
    "    return max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 2, 1, 1, 1, 1]\n",
      "[1, 2, 2, 1, 1, 1]\n",
      "[1, 2, 2, 3, 1, 1]\n",
      "[1, 2, 2, 3, 4, 1]\n",
      "[1, 2, 2, 3, 4, 3]\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "4"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "lis([1,3,2,5,6,4])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem: length of the longest common sub-sequence\n",
    "\n",
    "Given 2 strings a,b return the length of the longest common sub-sequence.\n",
    "\n",
    "Example: 'abcde','ace' --> 3\n",
    "\n",
    "Induction rule:\n",
    "Let dp[i][j] denote the solution for a[i:],b[j:]. Then the following induction holds:\n",
    "\n",
    "dp[i][j] = 1+dp[i+1][j+1] if a[i]==b[j] else max(dp[i+1][j],dp[i][j+1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [],
   "source": [
    "def lcss(a,b):\n",
    "    dp = [[0]*(1+len(b)) for _ in range(1+len(a))]\n",
    "    for i in range(len(a))[::-1]:\n",
    "        for j in range(len(b))[::-1]:\n",
    "            if a[i]==b[j]:\n",
    "                dp[i][j] = 1+dp[i+1][j+1]\n",
    "            else:\n",
    "                dp[i][j] = max(dp[i+1][j],dp[i][j+1])\n",
    "    return dp[0][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "lcss('abcde','ace')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem: length of the longest common substring\n",
    "\n",
    "This is almost the same problem as the longest common sub-sequence with the difference that we're looking for a common contiguous string.\n",
    "\n",
    "Example: \n",
    "'abcde','ace' --> 1 (!)\n",
    "'abcde','bcd' --> 3\n",
    "\n",
    "The induction rule here is almost the same as above, with the difference that we don't use the else statement:\n",
    "\n",
    "Let dp[i][j] be the solution for a[i],b[j]. Then: \n",
    "\n",
    "dp[i][j] = 1+dp[i+1][j+1] if a[i]==b[j] (no else statement)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [],
   "source": [
    "def lcssg(a,b):\n",
    "    dp = [[0]*(1+len(b)) for _ in range(1+len(a))]\n",
    "    for i in range(len(a))[::-1]:\n",
    "        for j in range(len(b))[::-1]:\n",
    "            if a[i]==b[j]:\n",
    "                dp[i][j]=1+dp[i+1][j+1]\n",
    "    return max( [max(row) for row in dp] )"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 37,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "lcssg('abcde','bcd')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem: number of combinations to make x\n",
    "\n",
    "Given nums and x, return the number of combinations of nums that sum to x.\n",
    "\n",
    "Example: \\\n",
    "9,[3,5] --> 1 \\\n",
    "9,[5] --> 0 \\\n",
    "9,[1,3] --> 19 \\\n",
    "etc\n",
    "\n",
    "As always, let's first spell out the induction rule:\n",
    "\n",
    "Lets denote dp[i] the solution for target=i. Then:\n",
    "\n",
    "**dp[i] = Sum( dp[i-num] for num in nums if (i-num)>=0 )**\n",
    "\n",
    "In words: in order to arrive at i, consider all (i-num) and sum them."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {},
   "outputs": [],
   "source": [
    "def num_combis(x,nums):\n",
    "    dp = [1] + [0]*x\n",
    "    for i in range(x+1):\n",
    "        for num in nums:\n",
    "            if x-num>=0:\n",
    "                dp[i]+=dp[i-num]\n",
    "        print(dp)\n",
    "    return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 0, 0, 0, 0, 0, 0, 0, 0, 0]\n",
      "[1, 0, 0, 0, 0, 0, 0, 0, 0, 0]\n",
      "[1, 0, 1, 0, 0, 0, 0, 0, 0, 0]\n",
      "[1, 0, 1, 1, 0, 0, 0, 0, 0, 0]\n",
      "[1, 0, 1, 1, 1, 0, 0, 0, 0, 0]\n",
      "[1, 0, 1, 1, 1, 2, 0, 0, 0, 0]\n",
      "[1, 0, 1, 1, 1, 2, 2, 0, 0, 0]\n",
      "[1, 0, 1, 1, 1, 2, 2, 3, 0, 0]\n",
      "[1, 0, 1, 1, 1, 2, 2, 3, 4, 0]\n",
      "[1, 0, 1, 1, 1, 2, 2, 3, 4, 5]\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "5"
      ]
     },
     "execution_count": 51,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "num_combis(9,[3,2])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.9.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}