2D Dynamic Programming.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "2a3444d6",
   "metadata": {},
   "source": [
    "# Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a54d0162",
   "metadata": {},
   "source": [
    "## Unique Paths\n",
    "\n",
    "* https://leetcode.com/problems/unique-paths/description/\n",
    "***\n",
    "* Time Complexity:\n",
    "    - naive: O(2$^{m * n}$)\n",
    "        * for every cell, you have 2 options: you either go down or you go to the right\n",
    "        * there are m * n cells and 2 options for each cell\n",
    "    - topdown memo: O(m x n)\n",
    "        * unlike the naive, you aren't repeating any work and return immediately so you only visit each cell once\n",
    "    - bottom up: O(m x n)\n",
    "        * you have 2 loops going from 1...m and 1...n\n",
    "* Space Complexity:\n",
    "    - naive: O(m + n)\n",
    "        * you will have at most O(m + n) functions in the stack b/c you can go all the way down to the m-th row and go all the way to the right to the n-th column\n",
    "    - topdown memo: O(m x n)\n",
    "        * requires space for the 2D dp table\n",
    "    - bottom up: O(m x n)\n",
    "        * requires space for the 2D dp table\n",
    "***\n",
    "* naive:\n",
    "    - basically dfs/backtracking\n",
    "    - you either go down or you go right at each cell\n",
    "    - if you reach the bottom-right where the finish line is, then increment the numWays\n",
    "    - else, the number of ways to reach that cell is equal to the number of ways to reach the cell above and to the right of it\n",
    "        * numWays[r][c] = numWays[r + 1][c] + numWays[r][c + 1]\n",
    "* topdown memo:\n",
    "    - during the dfs/backtracking, we can actually reach the same cells we've already traversed on so we're just repeating work\n",
    "    - thus we can use a dp table to keep track of which cells we already have numWays on\n",
    "    - if we reach a cell that we've seen, we just return the numWays without traversing it again\n",
    "* bottom up:\n",
    "    - the concept is the same as topdown memo but we realize a couple of things:\n",
    "        1. we know that all the cells in the top rown, at row 0, are going to have 1 as their numWays\n",
    "            * reason being, you cannot reach them unless you keep going right\n",
    "        2. the same is true for all the cells in the first column, at col 0\n",
    "            * you cannot reach those cells unless you keep going down\n",
    "    - we can use that to our advantage and ask ourselves\n",
    "        * we know that the numWays[r][c] = numWays[r + 1][c] + numWays[r][c + 1]\n",
    "        * but since we start from the beginning and work our way to the bottom-right then this must be reversed\n",
    "        * so our __recurrence relation__ must be:\n",
    "            - __dp[r][c] = dp[r - 1][c] + dp[r][c - 1]__\n",
    "            - since we've already calculated the cells in the first row and first col, we can use those tabulated values already to calculate newer cells"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "b3e0fa65",
   "metadata": {},
   "outputs": [],
   "source": [
    "/**\n",
    " * @param {number} m\n",
    " * @param {number} n\n",
    " * @return {number}\n",
    " */\n",
    "\n",
    " // naive dfs/backtracking\n",
    "var uniquePaths = function(m, n) {\n",
    "    let numWays = 0;\n",
    "\n",
    "    const traverse = (r, c) => {\n",
    "        if (r >= m || c >= n) {\n",
    "            return;\n",
    "        }\n",
    "        if ((r === m - 1) && (c === n - 1)) {\n",
    "            numWays++;\n",
    "        }\n",
    "\n",
    "        // go down\n",
    "        traverse(r + 1, c);\n",
    "\n",
    "        // or go right\n",
    "        traverse(r, c + 1);\n",
    "    }\n",
    "\n",
    "    traverse(0, 0);\n",
    "    return numWays;\n",
    "};\n",
    "\n",
    "// naive dfs/backtracking\n",
    "var uniquePaths = function(m, n) {\n",
    "    const traverse = (r, c, numWays) => {\n",
    "        if (r < 0 || c < 0) {\n",
    "            return 0;\n",
    "        }\n",
    "        if (r === 0 && c === 0) {\n",
    "            numWays++;\n",
    "            return numWays;\n",
    "        }\n",
    "\n",
    "        return traverse(r - 1, c, numWays) + traverse(r, c - 1, numWays);\n",
    "    }\n",
    "\n",
    "    return traverse(m - 1, n - 1, 0);\n",
    "};\n",
    "\n",
    "// topdown memo\n",
    "var uniquePaths = function(m, n) {\n",
    "    const dp = Array.from({length: m}, () => Array.from({length: n}));\n",
    "\n",
    "    const traverse = (r, c, numWays) => {\n",
    "        if (r < 0 || c < 0) {\n",
    "            return 0;\n",
    "        }\n",
    "        if (r === 0 && c === 0) {\n",
    "            numWays++;\n",
    "            return numWays;\n",
    "        }\n",
    "        if (dp[r][c] !== undefined) {\n",
    "            return dp[r][c];\n",
    "        }\n",
    "\n",
    "        dp[r][c] = traverse(r - 1, c, numWays) + traverse(r, c - 1, numWays);\n",
    "        return dp[r][c];\n",
    "    }\n",
    "\n",
    "    // console.log({dp})\n",
    "    return traverse(m - 1, n - 1, 0);\n",
    "};\n",
    "\n",
    "// bottom-up dp\n",
    "var uniquePaths = function(m, n) {\n",
    "    const dp = Array.from({length: m}, () => Array.from({length: n}));\n",
    "\n",
    "    for (let r = 0; r < m; r++) {\n",
    "        dp[r][0] = 1;\n",
    "    }\n",
    "\n",
    "    for (let c = 0; c < n; c++) {\n",
    "        dp[0][c] = 1;\n",
    "    }\n",
    "\n",
    "    for (let r = 1; r < m; r++) {\n",
    "        for (let c = 1; c < n; c++) {\n",
    "            dp[r][c] = dp[r - 1][c] + dp[r][c - 1];\n",
    "        }\n",
    "    }\n",
    "\n",
    "    return dp[m - 1][n - 1];\n",
    "}\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "941f049f",
   "metadata": {},
   "source": [
    "## Longest Common Subsequence\n",
    "\n",
    "* https://leetcode.com/problems/longest-common-subsequence/description/\n",
    "***\n",
    "* Time Complexity:\n",
    "    - naive: O(2$^{n}$)\n",
    "        * if text1[i] !== text2[j], then we have 2 choices to traverse: [i + 1, j] or [i, j + 1]\n",
    "            - essentially, we disregard text1[i] and instead look at subsequence from text1[i + 1...n]\n",
    "            - or disregard text2[j] and look at subsequence from text2[j + 1...n]\n",
    "    - topdown memo: O(m x n), where m = length of text1 and n = length of text2\n",
    "        * by using a dp table, we immediately solve any overlapping subproblems\n",
    "        * thus we only need to solve for all subproblems of [i,j]\n",
    "            - and since i = m and j = n, we have to solve m x n total problems\n",
    "    - bottom up: O(m x n)\n",
    "        * similar to the topdown memo\n",
    "        * we fill out a table and solve m x n total problems to get the answer\n",
    "* Space Complexity:\n",
    "    - naive: O(max(m, n))\n",
    "        * uses recursion so we need space for the function stack\n",
    "        * when text1[i] !== text2[j] we have to traverse on [i + 1, j] and [i, j + 1]\n",
    "            - i is bounded by the length of text1 and j is bounded by the length of text2 since we return immediately when i and j are equal or greater than m and n respectively\n",
    "            - therefore, the max height of our recursion will be the max length between text1 and text2\n",
    "    - topdown memo: O(m x n)\n",
    "        * requires space for the dp table which is O(m x n)\n",
    "    - bottom up: O(m x n)\n",
    "        * requires space for the dp table which is O(m x n)\n",
    "***\n",
    "* I figured out the bottom up dp algorithm first before the naive/top down so i'll start with that\n",
    "* bottom up dp:\n",
    "    - visualize filling out a table where the rows represent the subsequences of text1 and the columns are subsequences of text2\n",
    "    - when we fill out the first row and the first column respectively, what are we actually doing?\n",
    "        * for the first row, we are checking if text1[0] is a subsequence of text2[0 ... n]\n",
    "        * for the first col, we are checking if text2[0] is a subsequence of text1[0...n]\n",
    "        * if at any point the first char of either of these texts are a subsequence of a section of the other text, then the rest of this text also contains that subsequence:\n",
    "            - e.g. text1 = 'bac', text2 = 'a'\n",
    "            - our first row would look like: [0, 1, 1]\n",
    "                * 'b' !== 'a'\n",
    "                * 'a' === 'a'\n",
    "                * 'c' !== 'a' BUT we know that the previous subsequence DOES contain at least 1 char so we include it even though the chars don't match\n",
    "    - once we fill out the first row and first col, we can then look at the __recurrence relation__:\n",
    "        * __dp[i][j] =__ \n",
    "            - __1 + dp[i - 1][j - 1], if text1[i] === text2[j]__\n",
    "            - __Math.max(dp[i - 1][j], dp[i, j - 1]), if text1[i] !== text2[j]__\n",
    "        * essentially, if the current strings match at i and j, then look at the previous subsequences of both and add 1 to them\n",
    "            - thus we look at dp[i - 1][j - 1]\n",
    "        * if they don't match, then we look at previous subsequences of either text\n",
    "            - dp[i - 1][j] = look at previous subsequences of text1\n",
    "            - dp[i][j - 1] = look at previous subsequences of text2\n",
    "* naive algorithm:\n",
    "    - essentially use the same recurrence relation but done recursively\n",
    "* dp algorithm:\n",
    "    - notice that we might be solving for the same [i,j] subsequences so we use a dp table to keep track of those values\n",
    "    - if we have already solved for it, then just return it"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "7ec10f37",
   "metadata": {},
   "outputs": [],
   "source": [
    "/**\n",
    " * @param {string} text1\n",
    " * @param {string} text2\n",
    " * @return {number}\n",
    " */\n",
    "\n",
    " // naive algorithm\n",
    " // Time: O(2^n)\n",
    " // Space: O(max(m, n))\n",
    "var longestCommonSubsequence = function(text1, text2) {\n",
    "    if (text1 === text2) return text1.length;\n",
    "\n",
    "    const traverse = (i, j) => {\n",
    "        if (i >= text1.length || j >= text2.length) return 0;\n",
    "\n",
    "        if (text1[i] === text2[j]) {\n",
    "            return 1 + traverse(i + 1, j + 1);\n",
    "        }\n",
    "        else {\n",
    "            return Math.max(\n",
    "                traverse(i + 1, j),\n",
    "                traverse(i, j + 1)\n",
    "            );\n",
    "        }\n",
    "    }\n",
    "\n",
    "    return traverse(0, 0);\n",
    "};\n",
    "\n",
    "\n",
    "// topdown memo\n",
    "// Time: O(m x n)\n",
    "// Space: O(m x n)\n",
    "var longestCommonSubsequence = function(text1, text2) {\n",
    "    if (text1 === text2) return text1.length;\n",
    "    const m = text1.length;\n",
    "    const n = text2.length;\n",
    "    const dp = Array.from({length: m}, () => []);\n",
    "\n",
    "    const traverse = (i, j) => {\n",
    "        if (i >= m || j >= n) return 0;\n",
    "        if (dp[i][j] !== undefined) {\n",
    "            return dp[i][j];\n",
    "        }\n",
    "\n",
    "        if (text1[i] === text2[j]) {\n",
    "            dp[i][j] = 1 + traverse(i + 1, j + 1);\n",
    "        }\n",
    "        else {\n",
    "            dp[i][j] = Math.max(\n",
    "                traverse(i + 1, j),\n",
    "                traverse(i, j + 1)\n",
    "            );\n",
    "        }\n",
    "\n",
    "        return dp[i][j];\n",
    "    }\n",
    "\n",
    "    return traverse(0, 0);\n",
    "};\n",
    "\n",
    "// bottom up\n",
    "// Time: O(m x n)\n",
    "// Space: O(m x n)\n",
    "var longestCommonSubsequence = function(text1, text2) {\n",
    "    if (text1 === text2) return text1.length;\n",
    "\n",
    "    // create the dp table\n",
    "    const m = text1.length;\n",
    "    const n = text2.length;\n",
    "    const dp = Array.from({length: m}, () => []);\n",
    "\n",
    "    // fill out the first row and first col\n",
    "    dp[0][0] = text1[0] === text2[0] ? 1 : 0;\n",
    "\n",
    "    // row\n",
    "    for (let i = 1; i < m; i++) {\n",
    "        dp[i][0] = text1[i] === text2[0] ? 1 : dp[i - 1][0];\n",
    "    }\n",
    "\n",
    "    // col\n",
    "    for (let j = 1; j < n; j++) {\n",
    "        dp[0][j] = text1[0] === text2[j] ? 1 : dp[0][j - 1];\n",
    "    }\n",
    "\n",
    "    // looping through the entire table\n",
    "    for (let i = 1; i < m; i++) {\n",
    "        for (let j = 1; j < n; j++) {\n",
    "            if (text1[i] === text2[j]) {\n",
    "                dp[i][j] = 1 + dp[i - 1][j - 1];\n",
    "            }\n",
    "            else {\n",
    "                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);\n",
    "            }\n",
    "        }\n",
    "    }\n",
    "\n",
    "    return dp[m - 1][n - 1];\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0e7b7028",
   "metadata": {},
   "source": [
    "## Best Time to Buy and Sell Stock with Cooldown\n",
    "\n",
    "* https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/description/\n",
    "***\n",
    "* Time Complexity: O(n)\n",
    "    - basically we just traverse from [0...n]\n",
    "    - our dp table helps us to maintain O(n) complexity b/c of the key\n",
    "        * normally it would be around O(2$^{n}$) b/c for each index from 0 to n, we can make 2 decisions:\n",
    "            - if we haven't bought, we can buy or cooldown\n",
    "            - if we have bought, we can sell or cooldown\n",
    "            - if we have already sold, we must cooldown but this case is taken care of by skipping over the next index and going to index + 2\n",
    "* Space Complexity: O(n)\n",
    "    - needs space for the dp table\n",
    "***\n",
    "* __FOR THESE STOCK TYPE QUESTIONS WE MUST BE AWARE OF THREE STATES: BUY, SELL, HOLD__\n",
    "* if we draw out a decision tree, each node in the tree represents an index and we have several options\n",
    "    - i = 0: we can either buy or hold\n",
    "        * we can't sell b/c we haven't bought anything\n",
    "        * and we can ALWAYS HOLD (just do nothing)\n",
    "    - i = 1:\n",
    "        * if we bought at i = 0, we can either sell or cooldown\n",
    "        * if we hold at i = 0, we can either buy or cooldown\n",
    "    - i = 2:\n",
    "        * if we hold at i = 1, we can either buy or cooldown\n",
    "        * if we bought at i = 1, we can either sell or cooldown\n",
    "        * if we sold at i = 1, WE MUST COOLDOWN which means this index would've been skipped and we would've arrived at i = 3 if this was the case\n",
    "* thus our __recurrence relation is so:__\n",
    "    * __dp[i][canBuy] = Math.max(dp[i + 1][!canBuy], dp[i + 1][canBuy]), if canBuy = true__\n",
    "        - basically if we are buying, then we have to look at the max ofif we sell or hold on the next stock\n",
    "    * __dp[i][canBuy] = Math.max(dp[i + 2][!canBuy], dp[i + 1][canBuy]), if canBuy = false__\n",
    "        - basically if we are selling, we HAVE to take a cooldown and look at the max profit starting at i + 2 and if we decided to cooldown and not sell at i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "61527b9c",
   "metadata": {},
   "outputs": [],
   "source": [
    "/**\n",
    " * @param {number[]} prices\n",
    " * @return {number}\n",
    " */\n",
    "\n",
    " // Time Complexity: O(n)\n",
    " // Space Complexity: O(n)\n",
    "var maxProfit = function(prices) {\n",
    "    if (prices.length === 1) return 0;\n",
    "\n",
    "    // key = 'index-boolean', val = max profit\n",
    "    // e.g. 0-true, 10\n",
    "    const dp = new Map();\n",
    "\n",
    "    const traverse = (i, canBuy) => {\n",
    "        if (i >= prices.length) return 0;\n",
    "        \n",
    "        const key = `${i}${canBuy}`\n",
    "        if (dp.has(key)) {\n",
    "            return dp.get(key);\n",
    "        }\n",
    "\n",
    "        // for our stock we can either buy, sell, or hold (cooldown)\n",
    "        // this basically represents branches in our decision tree\n",
    "        // however, we know that the problem has 1 constraint:\n",
    "        // you MUST cooldown after you sell for at least 1 day (or 1 index)\n",
    "        // so in order to accommodate for this, we must keep track of this state somehow\n",
    "\n",
    "        // regardless of if we've bought or sold before\n",
    "        // we can ALWAYS choose the option to cooldown or hold\n",
    "        let cooldown = traverse(i + 1, canBuy);\n",
    "        \n",
    "        // if we are allowed to buy\n",
    "        if (canBuy) {\n",
    "            // we subtract prices[i] b/c we are LOSING profit by buying the stock\n",
    "            // we traverse to the next index and we set the boolean to false\n",
    "            // b/c we've already bought and do NOT want to buy again\n",
    "            let buy = traverse(i + 1, false) - prices[i];\n",
    "            dp.set(key, Math.max(buy, cooldown));\n",
    "        }\n",
    "        else {\n",
    "            // since we are selling the stock, the next state MUST be to cooldown\n",
    "            // so that's why we move 2 indices away\n",
    "            // and we add prices[i] b/c we MADE profit (maybe) by selling the stock\n",
    "            // we also set buying to true here b/c we've already sold\n",
    "            // we're allowed to do it after we've cooldowned\n",
    "            let sell = traverse(i + 2, true) + prices[i];\n",
    "            dp.set(key, Math.max(sell, cooldown));\n",
    "        }\n",
    "\n",
    "        return dp.get(key);\n",
    "    }\n",
    "\n",
    "    return traverse(0, true);\n",
    "};"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "47a2ac5c",
   "metadata": {},
   "source": [
    "## Coin Change II\n",
    "\n",
    "* https://leetcode.com/problems/coin-change-ii/description/\n",
    "***\n",
    "* Time Complexity:\n",
    "    - naive: O(2$^{amount}$)\n",
    "        * you have 2 options for every coin\n",
    "            - don't include the coin in the combination to make the amount\n",
    "            - include the coin to make the amount\n",
    "            - and the height of the tree = amount b/c if you have coins = [1] and amount = 10, you will only have 1 branch that will go down all the way to the amount\n",
    "    - topdown memo: O(n * amount), where n = # of coins\n",
    "        * you essentially fill up your dp table but recursively\n",
    "        * and your dp table has O(n * amount) subproblems\n",
    "    - bottom-up dp: O(n * amount)\n",
    "        * also filling up a dp table but iteratively and there are O(n * amount) subproblems\n",
    "* Space Complexity:\n",
    "    - naive: O(amount)\n",
    "        * using recursion so you have to have space for the functions on the stack\n",
    "        * and the amount of functions on the stack is equal to the height of the tree which is O(amount)\n",
    "    - topdown memo: O(n * amount)\n",
    "        * requires space for your dp table\n",
    "        * also uses recursion but that is not the dominant term: O(amount)\n",
    "    - bottom-up dp: O(n * amount)\n",
    "        * requires space for your dp table\n",
    "    - bottom-up dp - space optimized: O(amount)\n",
    "        * the bottom-up solution only requires the current and previous rows which can just be squashed into one row\n",
    "        * so when we only use 1 row, our array is still the length of the amount + 1\n",
    "        * therefore, our space is O(amount)\n",
    "***\n",
    "* naive:\n",
    "    - we know that if the amount = 0, there is 1 COMBINATION that can make it, which is the __empty set__\n",
    "    - and similar to other backtracking/dfs problems we have TWO options:\n",
    "        * we can EXCLUDE the current coin and proceed to other coins after it with the same current amount\n",
    "        * we can INCLUDE the current coin and proceed to other coins after it\n",
    "    - in addition, the ORDER of the coins in the combination DOES NOT MATTER\n",
    "        * so if coins = [1,2] and amount = 4\n",
    "            - [1,1,2] = [1,2,1] = [2,1,1] even though the order is different\n",
    "        * __to solve this, we can pass in the INDEX so that if we have reached that coin's index, we only need to look at coins with an index AFTER that one and we don't backtrack on those__\n",
    "* topdown memo:\n",
    "    - we are actually repeating some subproblems so we can use a dp table to keep track of those and return immediately\n",
    "    - our dp table = dp[index][amount]\n",
    "        * dp[i][j] represents the amount of combinations that make the amount, j, using the first i coins\n",
    "* bottom-up dp:\n",
    "    - we have to be wary of a special case to initialize our dp table for bottom-up\n",
    "        * dp[0][0] = 1\n",
    "            - __if amount = 0, we can use the EMPTY SET__ to create this\n",
    "        * this also helps us to initialize this further by suggesting that dp[i][0] = 1 as well since the empty set will ALWAYS be a valid combination to make amount 0 regardless of how many coins we use\n",
    "        * and this also helps with initializing the first row as well since we know that dp[0][j] = 0 for j >= 1\n",
    "            - this is b/c we cannot make any amount > 0 with 0 coins\n",
    "    - once we've initialized, our __recurrence relation__ is:\n",
    "        * __dp[i][j] = dp[i - 1][j] + dp[i][j - coins[i - 1]]__\n",
    "            - dp[i - 1][j] = exclude the coin and only use the previous combination of coins\n",
    "            - dp[i][j - coins[i - 1]] = include the coin to create the amount\n",
    "                * __THE REASON WHY WE USE coins[i - 1] INSTEAD OF coins[i] IS B/C OF THE SPECIAL CASE OF THE EMPTY SET__\n",
    "                    - when i = 0, that represents using 0 coins to make the amount\n",
    "                    - when i = 1, that represents using the first coin to make the amount BUT THE FIRST COIN IS AT INDEX 0 IN COINS\n",
    "                        * so to account for this, we use coins[i - 1]\n",
    "                        * therefore, i = 1, coins[1 - 1] = coins[0]\n",
    "* bottom-up dp - space optimized:\n",
    "    - notice how our recurrence relation only uses the current and previous rows\n",
    "    - thus we can actually squish the entire table into just 1 row\n",
    "    - by doing this, our __optimized recurrence relation__ changes\n",
    "        * __dp[amount] = dp[amount] + dp[amount - coin]__\n",
    "            - since we only use 1 row for the entire dp algorithm, we can drop 1 dimension from our dp which just leaves us with the amount, j\n",
    "    - dropping the row dimension also allows us to change the outer loop to instead loop using values instead of the i index\n",
    "        * this bypasses the need for index compensation from the non-space optimized solution and simplifies the dp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "1adbf516",
   "metadata": {},
   "outputs": [],
   "source": [
    "/**\n",
    " * @param {number} amount\n",
    " * @param {number[]} coins\n",
    " * @return {number}\n",
    " */\n",
    "\n",
    "// naive\n",
    "var change = function(amount, coins) {\n",
    "    // there's only 1 COMBINATION to make 0\n",
    "    // it's basically the empty set\n",
    "    if (amount === 0) return 1;\n",
    "\n",
    "    const traverse = (index, curAmount) => {\n",
    "        if (curAmount > amount) return 0;\n",
    "        if (curAmount === amount) return 1;\n",
    "        if (index >= coins.length) return 0;\n",
    "\n",
    "        // index, curAmount + coins[index] => use the same coin and update the amount\n",
    "        // index + 1, curAmount => use a different coin but keep the same amount\n",
    "        return traverse(index, curAmount + coins[index]) + traverse(index + 1, curAmount); \n",
    "    }\n",
    "\n",
    "    return traverse(0, 0)\n",
    "};\n",
    "\n",
    "// topdown memo\n",
    "var change = function(amount, coins) {\n",
    "    if (amount === 0) return 1;\n",
    "    const dp = Array.from({length: coins.length}, () => []);\n",
    "\n",
    "    const traverse = (index, curAmount) => {\n",
    "        if (curAmount > amount) return 0;\n",
    "        if (curAmount === amount) return 1;\n",
    "        if (index >= coins.length) return 0;\n",
    "\n",
    "        if (dp[index][curAmount]) {\n",
    "            return dp[index][curAmount];\n",
    "        }\n",
    "\n",
    "        let ways = 0;\n",
    "        \n",
    "        // use the current coin until we reach the amount of over the amount\n",
    "        ways += traverse(index, curAmount + coins[index]);\n",
    "\n",
    "        // or we disregard current coin and move on to the ones after it\n",
    "        // by doing this, we also disregard dupes b/c we do not reuse any coins we've already used\n",
    "        ways += traverse(index + 1, curAmount);\n",
    "\n",
    "        dp[index][curAmount] = ways;\n",
    "\n",
    "        return dp[index][curAmount];\n",
    "    }\n",
    "\n",
    "    return traverse(0, 0);\n",
    "}\n",
    "\n",
    "// bottom-up dp\n",
    "var change = function(amount, coins) {\n",
    "    if (amount === 0) return 1;\n",
    "\n",
    "    // dp[0...coins.length][0...amount]\n",
    "    const dp = Array.from({length: coins.length + 1}, () => []);\n",
    "\n",
    "    // THIS IS A SPECIAL CASE\n",
    "    // WE CAN MAKE AMOUNT = 0 WHEN WE USE 0 COINS!!!\n",
    "    // remember that the Coin Change II problem asks for the NUMBER OF COMBINATIONS\n",
    "    // the EMPTY SET is a valid combination\n",
    "    dp[0][0] = 1;\n",
    "\n",
    "    for (let i = 1; i <= coins.length; i++) {\n",
    "        // we always have 1 combination that can make amount 0\n",
    "        // which is the EMPTY SET\n",
    "        dp[i][0] = 1;\n",
    "\n",
    "        for (let j = 1; j <= amount; j++) {\n",
    "            // the top row is initialized to 0 b/c there is no way to make any amount over 0\n",
    "            // using 0 coins\n",
    "            dp[0][j] = 0;\n",
    "\n",
    "            // we have the option of disregarding the current coin in the combination\n",
    "            // and only using combinations of the previous coins\n",
    "            dp[i][j] = dp[i - 1][j];\n",
    "\n",
    "            // the other option is to include the coin in the combination\n",
    "            // but we must determine if adding it will not be over the amount\n",
    "\n",
    "            // THE REASON WHY WE USE coins[i - 1] INSTEAD OF coins[i] IS BECAUSE OF THE SPECIAL CASE\n",
    "            // WHERE WE USE THE EMPTY SET (0 COINS)\n",
    "            // SO WHEN WE HAVE i = 0, THAT IS ACTUALLY NOT THE FIRST COIN\n",
    "            // THAT REPRESENTS WHEN WE USE 0 COINS\n",
    "            // i = 1 = when we use the FIRST COIN in coins even though i != 0\n",
    "            // therefore, we use coins[i - 1]. so if i = 1, then coins[1 - 1] = coins[0]\n",
    "            if (j - coins[i - 1] >= 0) {\n",
    "                dp[i][j] += dp[i][j - coins[i - 1]];\n",
    "            }\n",
    "        }\n",
    "    }\n",
    "\n",
    "    return dp[coins.length][amount];\n",
    "}\n",
    "\n",
    "// bottom-up dp space optimized\n",
    "var change = function(amount, coins) {\n",
    "    if (amount === 0) return 1;\n",
    "\n",
    "    // in the original bottom-up algorithm, we only ever needed the current and previous rows\n",
    "    // and not the entire table\n",
    "    // therefore, we can squeeze this into just 1 array\n",
    "    const dp = Array.from({length: amount + 1}, () => 0);\n",
    "    dp[0] = 1;\n",
    "\n",
    "    // the loop structure is very similar to Coin Change\n",
    "    for (let coin of coins) {\n",
    "        for (let amt = coin; amt <= amount; amt++) {\n",
    "            // this is basically the same as the previous recurrence relation but simplified\n",
    "            // it is essentially: dp[amt] = dp[amt] + dp[amt - coin];\n",
    "            // so we either disregard the current coin in the amt\n",
    "            // OR we use it\n",
    "\n",
    "            // and since we only use a 1D array here instead of a 2D, we can drop the row index\n",
    "            // and only use the amount index\n",
    "            // this is also why we do not need an i index for the outer loop and only grab the coin values\n",
    "\n",
    "            // and we do not need to check for any conditionals where it is out of bounds b/c\n",
    "            // we start off at amt = coin\n",
    "            // and if amt = coin, then amt - coin = 0\n",
    "            dp[amt] += dp[amt - coin];\n",
    "        }\n",
    "    }\n",
    "\n",
    "    return dp[amount];\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1db35f19",
   "metadata": {},
   "source": [
    "## Target Sum\n",
    "\n",
    "* https://leetcode.com/problems/target-sum/description/\n",
    "***\n",
    "* Time Complexity:\n",
    "    - naive: O(2$^{n}$), where n = length of nums\n",
    "        * basically backtracking/dfs\n",
    "        * at every node, you have 2 options:\n",
    "            - either add the number\n",
    "            - or you subtract the number\n",
    "        * and since you have to do this for every number in nums, the height of the tree is n\n",
    "    - topdown memo: O(n * target)\n",
    "        * you're essentially filling out a dp table\n",
    "        * and the dp table has O(n * target) subproblems\n",
    "    - bottom-up: O(n * target)\n",
    "        * also filling out a dp table and there are O(n * target) subproblems\n",
    "* Space Complexity:\n",
    "    - naive: O(n)\n",
    "        * uses recursion so requires space for the function stack\n",
    "        * there will be O(n) functions in the stack b/c the deepest a branch will go is equal to length of nums which is n\n",
    "    - topdown memo: O(n * target)\n",
    "        * requires space for the dp table\n",
    "        * also uses recursion\n",
    "    - bottom-up: O(target)\n",
    "        * dp table is equal to (target + sum + 1) * 2\n",
    "        * if target ~= sum, then this is basically target * 2 or O(target)\n",
    "***\n",
    "* naive:\n",
    "    - basically have 2 options:\n",
    "        * you add the current number\n",
    "        * or subtract the current number\n",
    "    - you do this until you've accounted for all the numbers in nums\n",
    "* topdown memo:\n",
    "    - you're actually doing duplicate work here so you can use a dp table to memoize some subproblems\n",
    "    - your dp table would then return if dp[index][sum] is already solved\n",
    "* bottom-up:\n",
    "    - the original problem can be summarized like so:\n",
    "        * find a subset of nums that need to be positive and the rest of them negative, such that the sum is equal to the target\n",
    "        * essentially: sum(Positve) - sum(Negative) = target\n",
    "    - we know that the Partition Equal Subset Sum's goal is thus: find a subset = target / 2\n",
    "        * using this goal, we can transform our equation to match this:\n",
    "            - sum(P) - sum(N) = target\n",
    "            - add sum(P) + sum(N) to both sides \n",
    "            - => 2 * sum(P) = target + sum(P) + sum(N)\n",
    "                * reason why we add sum(N) is b/c we want to just isolate sum(P) on the left side and get rid of sum(N)\n",
    "            - we can condense the right side => 2 * sum(P) = target + sum(nums)\n",
    "            - => __sum(P) = (target + sum(nums)) / 2__\n",
    "    - looking at this equation, we can also use this to check if we can get a solution with nums that will equal to target\n",
    "        * we know that sum(P) HAS to be an even number\n",
    "    - using that equation, we then create a dp table equal to that sum and initialize dp[0] = 1\n",
    "        * there will always exist a subset that will create a sum of 0, the empty set\n",
    "    - then we loop for every coin and for each coin, we loop from the sum...coin\n",
    "        * 2 reasons why we do this:\n",
    "            - this is a 0/1 knapsack, NOT UNBOUNDED KNAPSACK\n",
    "            - so to avoid REUSING the same coins infinitely, we count backwards from the sum since we haven't used those earlier sums yet.\n",
    "                * they've all been initialized to 0\n",
    "            - the second reason is that if we go from sum...coin instead of 0, we do not have to check the condition (num <= sum) b/c if sum = coin, then sum - coin = 0."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "14410320",
   "metadata": {},
   "outputs": [],
   "source": [
    "/**\n",
    " * @param {number[]} nums\n",
    " * @param {number} target\n",
    " * @return {number}\n",
    " */\n",
    "\n",
    "// naive\n",
    "var findTargetSumWays = function(nums, target) {\n",
    "    const traverse = (i, sum) => {\n",
    "        if (i >= nums.length) {\n",
    "            return sum === target ? 1 : 0;\n",
    "        }\n",
    "\n",
    "        return traverse(i + 1, sum + nums[i]) + traverse(i + 1, sum - nums[i]);\n",
    "    }\n",
    "\n",
    "    return traverse(0, 0);\n",
    "};\n",
    "\n",
    "// topdown memo\n",
    "var findTargetSumWays = function(nums, target) {\n",
    "    // dp[0...nums.length][0...target]\n",
    "    // the reason why we use a map is b/c we have to account for NEGATIVE targets\n",
    "    const dp = Array.from({length: nums.length}, () => new Map());\n",
    "\n",
    "    const traverse = (i, sum) => {\n",
    "        if (i >= nums.length) {\n",
    "            return sum === target ? 1 : 0;\n",
    "        }\n",
    "\n",
    "        if (dp[i].has(sum)) {\n",
    "            return dp[i].get(sum);\n",
    "        }\n",
    "        \n",
    "        dp[i].set(sum, traverse(i + 1, sum + nums[i]) + traverse(i + 1, sum - nums[i]));\n",
    "        return dp[i].get(sum);\n",
    "    }\n",
    "\n",
    "    return traverse(0, 0);\n",
    "};\n",
    "\n",
    "// bottom-up dp\n",
    "var findTargetSumWays = function(nums, target) {\n",
    "    let sum = 0;\n",
    "    nums.forEach(num => sum += num);\n",
    "\n",
    "    // if you can't even add all the numbers up to the target, then it can't be\n",
    "    // also, similar to the Partition Equal Subset Sum question, the sum of the\n",
    "    // positive (+) integers MUST be even\n",
    "    if (sum < Math.abs(target) || (sum + target) % 2 === 1) {\n",
    "        return 0;\n",
    "    }\n",
    "\n",
    "    // this is all essentially the same as Partition Equal Subset Sum\n",
    "    sum = Math.trunc((target + sum) / 2);\n",
    "    const dp = Array.from({length: sum + 1}, () => 0);\n",
    "    dp[0] = 1;\n",
    "\n",
    "    for (let num of nums) {\n",
    "        // if we go from sum ... num, then we do not need to check if the condition\n",
    "        // (num <= sum) is true so that we do not check for any index < 0\n",
    "        for (let i = sum; i >= num; i--) {\n",
    "                dp[i] += dp[i - num];\n",
    "        }\n",
    "    }\n",
    "\n",
    "    return dp[sum];\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8f0fc790",
   "metadata": {},
   "source": [
    "## Interleaving String\n",
    "\n",
    "* https://leetcode.com/problems/interleaving-string/description/\n",
    "***\n",
    "* Time Complexity:\n",
    "    - naive: O(2$^{m + n}$), where n = size of s1 and m = size of s2\n",
    "        * you have 2 options per node\n",
    "            - either use s1\n",
    "            - or use s2\n",
    "        * the recursion goes as deep as the length of s3, which is m + n\n",
    "    - topdown: O(m * n)\n",
    "        - essentially filling out a dp table the size of m * n\n",
    "    - bottom-up: O(m * n)\n",
    "        - filling out a dp table the size of m * n\n",
    "* Space Complexity:\n",
    "    - naive: O(m + n)\n",
    "        * uses recursion so needs space for the functions in the stack\n",
    "        * the recursion goes as deep as the length of s3, which is m + n\n",
    "    - topdown: O(m * n)\n",
    "        * needs space for a dp table which is m * n\n",
    "    - bottom-up: O(m * n)\n",
    "        * needs space for a dp table which is m * n\n",
    "    - bottom-up space optimized: O(m)\n",
    "        * only use the current and previous rows, dp[i] and dp[i - 1], respectively so we can condense the table down to just one row\n",
    "        * the length of the row is equal to s2 which is m\n",
    "***\n",
    "* naive:\n",
    "    - the interleaving part is confusing but essentially you are seeing if you can weave s1 and s2 to make s3\n",
    "        * the condition of |n - m| <= 1 is always going to be true\n",
    "        * take for example s1 = \"ab\", s2 = \"abad\", s3 = \"aabadb\"\n",
    "            - this is made by splitting s1 = \"a\" + \"b\" and putting s2 in the middle of that, so \"a\"(s1) + \"abad\"(s2) + \"b\"(s1)\n",
    "            - \"a\" is the first substring of s1 and \"abad\" is the first substring of s2, which are s1<sub>0</sub> and s2<sub>0</sub> respectively\n",
    "            - but if you decided to use the entirety of s1 and then s2, then s1<sub>0</sub> = \"ab\"\n",
    "            - in essence, __using s1 or s2 will either contribute to the current substring OR use a new substring__\n",
    "                * if you use s1 and the previous interleaving ALSO used s1, then that contributes to the substring\n",
    "                * but if you use s2 and the previous interleaving used s1, you are using a new substring of s2\n",
    "                * so either way, the constraint will ALWAYS be true\n",
    "    - so if we want to weave s1 and s2 together, we can do what we always do with dfs/backtracking\n",
    "        * either start with s1\n",
    "        * or start with s2\n",
    "        * but we also need to make sure of 1 thing, DOES THE CHARACTER EVEN MATCH THE ONE IN S3\n",
    "            - if s3[0] = \"a\" and s1[0] = \"b\", why would we continue traversing starting with s1?\n",
    "            - every interleaving using s1[0] will ALWAYS be false\n",
    "* topdown memo:\n",
    "    - we are actually repeating work in the naive algorithm so we can keep track of combinations of i and j that have interleaved already\n",
    "    - so our __recurrence relation__ is:\n",
    "        * __dp[i][j] = (dp[i + 1][j] && s1[i] === s3[i + j - 1]) || (dp[i][j + 1] && s2[j] === s3[i + j - 1]), where [i + j - 1] is the current index of s3__\n",
    "* bottom-up dp:\n",
    "    - essentially doing what the topdown memo is doing but in reverse\n",
    "    - in this algorith, 0 DOES NOT REPRESENT THE FIRST INDEX OF s1 or s2\n",
    "        * 0 = THE EMPTY SET, using 0 characters from s1 or s2\n",
    "    - dp[i][j] represents if we can interleave string s3[0...(i +j - 1)] using s1[0...i] and s2[0...j]\n",
    "        * THEREFORE dp[0][0] = true\n",
    "        * e.g. if s1 = \"\", s2 = \"\", and s3 = \"\" is TRUE\n",
    "            - s1 = 0, s2 = 0, then s3 MUST be 0\n",
    "    - so using this knowledge, we can create our dp table to be dp[n + 1][m + 1] in size, where n = s1.length and m = s2.length\n",
    "        * why do we use n + 1 and m + 1?\n",
    "        * b/c of the special case of dp[0][0]\n",
    "            - since it represents using no characters from either string, then dp[1][1] is using 1 character from both s1 and s2\n",
    "            - so we can think of it like a __SLICE__ operation\n",
    "    - to initialize the table:\n",
    "        * dp[0][0] = true\n",
    "        * dp[i][0] = dp[i - 1][0] && s1[i - 1] === s3[i + j - 1] for 1...s1.length\n",
    "            - if we only interleave with characters from s1\n",
    "            - basically, if the current character at s1 matches the current character at s3, then can we interleave with the current character at s1 AND the previous substring of s1?\n",
    "            - also we check s1[i - 1] B/C of the special case of dp[0][0]\n",
    "            - s1[0] is not the first character of s1.\n",
    "                * it represents the using no characters from s1\n",
    "                * so if i = 1, then s1[1 - 1] = the first character of s1\n",
    "        * dp[0][j] = dp[0][j - 1] && s2[j - 1] === s3[i + j - 1] for 1...s2.length\n",
    "            - same thing as s1 but for s2\n",
    "    - we then loop from 1...s1.length and 1...s2.length and check the __recurrence relation of the bottom-up dp:__\n",
    "        * __dp[i][j] = (dp[i - 1][j] && s1[i - 1] === s3[i + j - 1]) || (dp[i][j - 1] && s2[j - 1] === s3[i + j - 1])__\n",
    "* bottom-up space optimized:\n",
    "    - notice in the recurrence relation that we only ever use the current and previous rows, dp[i] and dp[i - 1]\n",
    "    - thus we can compress the entire table down into just 1 row and can remove AN ENTIRE DIMENSION from our recurrence relation\n",
    "    - __space optimized recurrence relation__:\n",
    "        * __dp[j] = (dp[j] && s1[i - 1] === s3[i + j - 1]) || (dp[j - 1] && s2[j - 1] === s3[i + j - 1])__\n",
    "        * we only remove the row dimension from our dp calls, i, and we keep the rest of the conditional intact since we still need to check if the characters of s1/s2 match with s3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "cb938f92",
   "metadata": {},
   "outputs": [],
   "source": [
    "/**\n",
    " * @param {string} s1\n",
    " * @param {string} s2\n",
    " * @param {string} s3\n",
    " * @return {boolean}\n",
    " */\n",
    "\n",
    " // naive algorithm\n",
    "var isInterleave = function(s1, s2, s3) {\n",
    "    const n = s1.length;\n",
    "    const m = s2.length;\n",
    "\n",
    "    if (n === 0 || m === 0) {\n",
    "        return s1 === s3 || s2 === s3;\n",
    "    }\n",
    "\n",
    "    const traverse = (i, j, k, str) => {\n",
    "        // console.log({i, j, k, str, isEqual: str === s3})\n",
    "        if (str.length === s3.length && (i === n && j === m)) return str === s3;\n",
    "        \n",
    "        let canInterleave = false;\n",
    "        \n",
    "        // start with s1\n",
    "        if (i < n && s1[i] === s3[k]) canInterleave ||= traverse(i + 1, j, k + 1,str + s1[i]);\n",
    "\n",
    "        // start with s2\n",
    "        if (j < m && s2[j] === s3[k]) canInterleave ||= traverse(i, j + 1, k + 1, str + s2[j]);\n",
    "\n",
    "        return canInterleave;\n",
    "    }\n",
    "\n",
    "    return traverse(0, 0, 0, \"\");\n",
    "};\n",
    "\n",
    "\n",
    "// topdown memo\n",
    "var isInterleave = function(s1, s2, s3) {\n",
    "    const n = s1.length;\n",
    "    const m = s2.length;\n",
    "\n",
    "    if (n === 0 || m === 0) {\n",
    "        return s1 === s3 || s2 === s3;\n",
    "    }\n",
    "\n",
    "    const dp = Array.from({length: n + 1}, () => []);\n",
    "\n",
    "    const traverse = (i, j, k, str) => {\n",
    "        if (str.length === s3.length && (i === n && j === m)) return str === s3;\n",
    "\n",
    "        if (dp[i][j] !== undefined) {\n",
    "            return dp[i][j];\n",
    "        }\n",
    "        \n",
    "        let canInterleave = false;\n",
    "        \n",
    "        // start with s1\n",
    "        if (i < n && s1[i] === s3[k]) canInterleave ||= traverse(i + 1, j, k + 1,str + s1[i]);\n",
    "\n",
    "        // start with s2\n",
    "        if (j < m && s2[j] === s3[k]) canInterleave ||= traverse(i, j + 1, k + 1, str + s2[j]);\n",
    "\n",
    "        dp[i][j] = canInterleave;\n",
    "\n",
    "        return dp[i][j];\n",
    "    }\n",
    "\n",
    "    return traverse(0, 0, 0, \"\");\n",
    "};\n",
    "\n",
    "// bottom-up dp\n",
    "var isInterleave = function(s1, s2, s3) {\n",
    "    const n = s1.length;\n",
    "    const m = s2.length;\n",
    "\n",
    "    // must interleave the entirety of s1 and s2\n",
    "    // so if their lengths don't even match s3, then it cannot be interleaved\n",
    "    if (n + m < s3.length) return false;\n",
    "\n",
    "    // in the case where s1 = \"abc\", s2 = \"\", s3 = \"abc\"\n",
    "    if (n === 0 || m === 0) {\n",
    "        return s1 === s3 || s2 === s3;\n",
    "    }\n",
    "\n",
    "    // dp[0][0] index represents using NO characters\n",
    "    // NOT taking the first indices from each string\n",
    "    const dp = Array.from({length: n + 1}, () => []);\n",
    "\n",
    "    // we use no characters from either s1 or s2\n",
    "    dp[0][0] = true;\n",
    "\n",
    "    // since 0 represents using no characters\n",
    "    // s1[0] !== first character in s1\n",
    "    // s1[i - 1] = first character\n",
    "    for (let i = 1; i <= n; i++) {\n",
    "        dp[i][0] = dp[i - 1][0] && (s1[i - 1] === s3[i - 1]);\n",
    "    }\n",
    "\n",
    "    for (let j = 1; j <= m; j++) {\n",
    "        dp[0][j] = dp[0][j - 1] && (s2[j - 1] === s3[j - 1]);\n",
    "    }\n",
    "\n",
    "    for (let i = 1; i <= n; i++) {\n",
    "        for (let j = 1; j <= m; j++) {\n",
    "            dp[i][j] = false;\n",
    "\n",
    "            // start with s1\n",
    "            dp[i][j] ||= (dp[i - 1][j] && s1[i - 1] === s3[i + j - 1]);\n",
    "\n",
    "            // start with s2\n",
    "            dp[i][j] ||= (dp[i][j - 1] && s2[j - 1] === s3[i + j - 1]);\n",
    "        }\n",
    "    }\n",
    "\n",
    "    return dp[n][m];\n",
    "}\n",
    "\n",
    "// bottom-up dp - space optimized\n",
    "var isInterleave = function(s1, s2, s3) {\n",
    "    const n = s1.length;\n",
    "    const m = s2.length;\n",
    "\n",
    "    // must interleave the entirety of s1 and s2\n",
    "    // so if their lengths don't even match s3, then it cannot be interleaved\n",
    "    if (n + m < s3.length) return false;\n",
    "\n",
    "    // in the case where s1 = \"abc\", s2 = \"\", s3 = \"abc\"\n",
    "    if (n === 0 || m === 0) {\n",
    "        return s1 === s3 || s2 === s3;\n",
    "    }\n",
    "\n",
    "    // dp[0][0] index represents using NO characters\n",
    "    // NOT taking the first indices from each string\n",
    "\n",
    "    // notice from earlier that we only ever use the current row or the previous row\n",
    "    // so basically only i and i - 1\n",
    "    // therefore, we can reduce the space down to just 1 row\n",
    "    const dp = Array.from({length: m + 1});\n",
    "\n",
    "    // by removing 1 row, we can remove a dimension ENTIRELY\n",
    "    // so dp[i][j] can be condensed down to dp[j]\n",
    "    for (let i = 0; i <= n; i++) {\n",
    "        for (let j = 0; j <= m; j++) {\n",
    "            if (i === 0 && j === 0) {\n",
    "                dp[j] = true;\n",
    "            }\n",
    "            else if (i === 0) {\n",
    "                dp[j] = dp[j - 1] && s2[j - 1] === s3[i + j - 1];\n",
    "            }\n",
    "            else if (j === 0) {\n",
    "                dp[j] = dp[j] && s1[i - 1] === s3[i + j - 1];\n",
    "            }\n",
    "            else {\n",
    "                dp[j] = (dp[j - 1] && s2[j - 1] === s3[i + j - 1]) || (dp[j] && s1[i - 1] === s3[i + j - 1]);\n",
    "            }\n",
    "        }\n",
    "    }\n",
    "\n",
    "    return dp[m];\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a48cc5f9",
   "metadata": {},
   "source": [
    "## Unique Paths II\n",
    "\n",
    "* https://leetcode.com/problems/unique-paths-ii/description/\n",
    "***\n",
    "* Time Complexity:\n",
    "    - naive: O(2$^{m x n}$)\n",
    "        * for every cell that you encounter, you have 2 options:\n",
    "            1. go down [r + 1][c]\n",
    "            2. or go right [r][c + 1]\n",
    "        * this naive algorithm will encounter all cells\n",
    "    - topdown memo: O(m x n)\n",
    "        * the algorithm will still either go down or right but now it will return from any cells it has already encountered\n",
    "        * by not repeating this work, you will effectively visit every cell but now going down or right will not occur unless it is a new cell\n",
    "        * this reduces the time complexity significantly\n",
    "    - bottom-up dp: O(m x n)\n",
    "        * filling out the dp table will have us visit each cell in obstacleGrid\n",
    "* Space Complexity:\n",
    "    - naive: O(m + n)\n",
    "        * uses recursion so requires some space for the function calls in the stack\n",
    "        * the number of function calls is bounded by the numRows + numCols in obstacleGrid\n",
    "            - reason being, if you look at the recursion, you'll notice that it will recurse all the way down the grid first (numRows), then it would recurse all the way to the right (numCols)\n",
    "            - and once it reaches obstacleGrid[numRows - 1][numCols - 1] it will return\n",
    "            - so this is essentially numRows + numCols\n",
    "    - topdown memo: O(m x n)\n",
    "        * requires space for recursion, O(m + n)\n",
    "        * requires space for the memo table which is basically for each cell in obstacleGrid\n",
    "    - bottom-up dp: O(m x n)\n",
    "        * requires space for the dp table\n",
    "***\n",
    "* naive:\n",
    "    - base case:\n",
    "        * we know that if we reach an obstacle or we go out of bounds (OoB), then we have to return 0 b/c there are 0 ways to reach that cell\n",
    "        * and if we reach obstacleGrid[numRows - 1][numCols - 1] we return 1\n",
    "            - however, this condition occurs AFTER checking if obstacleGrid[numRows - 1][numCols - 1] === 1\n",
    "            - this is b/c if the last cell in obstacleGrid is an obstacle itself, then there is no way to reach it\n",
    "    - after we go through those conditions, we traverse to the right and left\n",
    "* topdown memo:\n",
    "    - our naive algorithm does not account for cells that we have encountered already so it will duplicate work\n",
    "    - in order to avoid this, we create a memo table and return if we have already seen it\n",
    "    - memo[r][c] represents the # of ways we reach last cell of obstacleGrid from [r, c]\n",
    "* bottom-up dp:\n",
    "    - looking at what we've done for the naive and memoized algorithms, we can determine our __recurrence relation__ to be:\n",
    "        * __dp[r][c] = dp[r - 1][c] + dp[r][c - 1]__\n",
    "        * dp[r][c] represents the # of ways to get to obstacleGrid[r][c] b/c we want to eventually return dp[numRows - 1][numCols - 1]\n",
    "        * therefore, our base case would be dp[0][0] = 0 or 1 depending on if obstacleGrid[r][c] is an obstacle itself\n",
    "        * we can then use dp[0][0] as a starting point to fill out row 0 and col 0\n",
    "            - for row, dp[r][0] = dp[r - 1][0] or 0 if obstacleGrid[r][0] is an obstacle\n",
    "            - for col, dp[0][c] = dp[0][c - 1] or 0 if obstacleGrid[0][c] is an obstacle\n",
    "        * this is the reason why our recurrence relation is dp[r - 1][c] and dp[r][c - 1] instead of dp[r + 1][c] or dp[r][c + 1] \n",
    "            - since we start from dp[0][0] and we loop from [1...numRows] and [1...numCols] we have not even solved for dp[r + 1][c] or dp[r][c + 1] yet\n",
    "            - we must therefore look at previous dp values to solve new ones"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "a4cfa72b",
   "metadata": {},
   "outputs": [],
   "source": [
    "/**\n",
    " * @param {number[][]} obstacleGrid\n",
    " * @return {number}\n",
    " */\n",
    "\n",
    " // naive\n",
    "var uniquePathsWithObstacles = function(obstacleGrid) {\n",
    "    const numRows = obstacleGrid.length;\n",
    "    const numCols = obstacleGrid[0].length;\n",
    "\n",
    "    const traverse = (r, c) => {\n",
    "        // OoB or in obstacle\n",
    "        if ((r < 0 || r >= numRows) ||\n",
    "            (c < 0 || c >= numCols) ||\n",
    "            (obstacleGrid[r][c] === 1)) {\n",
    "                return 0;\n",
    "        }\n",
    "\n",
    "        if (r === numRows - 1 && c === numCols - 1) {\n",
    "            return 1;\n",
    "        }\n",
    "\n",
    "        return traverse(r + 1, c) + traverse(r, c + 1); \n",
    "    }\n",
    "\n",
    "    return traverse(0, 0);\n",
    "};\n",
    "\n",
    "// topdown memo\n",
    "var uniquePathsWithObstacles = function(obstacleGrid) {\n",
    "    const numRows = obstacleGrid.length;\n",
    "    const numCols = obstacleGrid[0].length;\n",
    "    const memo = Array.from({length: numRows}, () => []);\n",
    "\n",
    "    const traverse = (r, c) => {\n",
    "        // OoB or an obstacle\n",
    "        if ((r < 0 || r >= numRows) ||\n",
    "            (c < 0 || c >= numCols) ||\n",
    "            (obstacleGrid[r][c] === 1)) {\n",
    "                return 0;\n",
    "        }\n",
    "\n",
    "        if (memo[r][c] !== undefined) {\n",
    "            return memo[r][c];\n",
    "        }\n",
    "\n",
    "        // if we reach the end\n",
    "        if (r === numRows - 1 && c === numCols - 1) {\n",
    "            return 1;\n",
    "        }\n",
    "\n",
    "        memo[r][c] = traverse(r + 1, c) + traverse(r, c + 1); \n",
    "        return memo[r][c];\n",
    "    }\n",
    "\n",
    "    return traverse(0, 0);\n",
    "};\n",
    "\n",
    "\n",
    "var uniquePathsWithObstacles = function(obstacleGrid) {\n",
    "    const numRows = obstacleGrid.length;\n",
    "    const numCols = obstacleGrid[0].length;\n",
    "\n",
    "    const dp = Array.from({ length: numRows}, () => []);\n",
    "\n",
    "    // dp[r][c] = # ways to get to obstacleGrid[r][c]\n",
    "\n",
    "    // we know that there is 1 way to get to obstacleGrid[0][0]\n",
    "    // UNLESS THE STARTING AREA IS AN OBSTACLE ITSELF\n",
    "    dp[0][0] = obstacleGrid[0][0] === 1 ? 0 : 1;\n",
    "\n",
    "    // fill out all rows\n",
    "    for (let r = 1; r < numRows; r++) {\n",
    "        // if dp[0][0] is an obstacle\n",
    "        // there is no way to reach these later cells\n",
    "        \n",
    "        if (obstacleGrid[r][0] === 1) {\n",
    "            dp[r][0] = 0;\n",
    "        }\n",
    "        else {\n",
    "            dp[r][0] = dp[r - 1][0];\n",
    "        }\n",
    "    }\n",
    "\n",
    "    // fill out all cols\n",
    "    for (let c = 1; c < numCols; c++) {\n",
    "        // if dp[0][0] is an obstacle\n",
    "        // there is no way to reach these later cells\n",
    "        \n",
    "        if (obstacleGrid[0][c] === 1) {\n",
    "            dp[0][c] = 0;\n",
    "        }\n",
    "        else {\n",
    "            dp[0][c] = dp[0][c - 1];\n",
    "        }\n",
    "    }\n",
    "\n",
    "    // since we require dp[r - 1][c] and dp[r][c - 1]\n",
    "    // it is wise to loop in the opposite direction of your recurrence relation\n",
    "\n",
    "    // since we've already solved all dp[0...numRows][0] and dp[0][0...numCols]\n",
    "    // we can use these previous cells to solve newer cells\n",
    "    for (let r = 1; r < numRows; r++) {\n",
    "        for (let c = 1; c < numCols; c++) {\n",
    "            if (obstacleGrid[r][c] === 1) {\n",
    "                dp[r][c] = 0;\n",
    "            }\n",
    "            else {\n",
    "                dp[r][c] = dp[r - 1][c] + dp[r][c - 1];\n",
    "            }\n",
    "        }\n",
    "    }\n",
    "\n",
    "    return dp[numRows - 1][numCols - 1];\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6f5e8bbe",
   "metadata": {},
   "source": [
    "## Minimum Path Sum\n",
    "\n",
    "* https://leetcode.com/problems/minimum-path-sum/description/\n",
    "***\n",
    "* Time Complexity:\n",
    "    - naive: O(2$^{m + n}$)\n",
    "        * for every node, you have 2 options:\n",
    "            - go down\n",
    "            - go right\n",
    "        * since, we only have these 2 options, if we start at [0, 0], we'll go all the way down first until we reach numRows, then we'll go all the way to the right until we reach [numRows - 1, numCols - 1]\n",
    "            - this means the recursion will return when we go m + n times\n",
    "    - topdown memo: O(m x n)\n",
    "        * by memoizing, we only visit each cell once and there are m x n cells in grid\n",
    "    - bottom-up dp: O(m x n)\n",
    "        * we also visit every cell once\n",
    "* Space Complexity:\n",
    "    - naive: O(m + n)\n",
    "        * uses recursion so requires space for functions in the stack\n",
    "        * the number of functions in the stack is bounded by how deep the recursion goes\n",
    "            - since we know that it will return once we go m + n times, the recursion is bounded by m + n functions\n",
    "    - topdown memo: O(m x n)\n",
    "        * requires space for the memo table\n",
    "    - bottom-up dp: O(m x n)\n",
    "        * requires space for the dp table\n",
    "***\n",
    "* naive:\n",
    "    - pretty typical dp algorithm\n",
    "    - we have 2 options, we either go down or go right\n",
    "    - everytime we recurse, we keep track of a sum\n",
    "    - when we go OoB, however, we return $\\infty$, not the sum itself\n",
    "        * reason being, if we just returned the original sum, Math.min would take that sum since as we traverse, our original sum gets bigger\n",
    "        * by returning $\\infty$, we make the algorithm disregard the OoB values\n",
    "* topdown memo:\n",
    "    - we have to change our algorithm here b/c the memo table actually doesn't do anything if we keep the algorithm the same\n",
    "        * reason being, our naive algorithm keeps track of a sum as we move from [0,0] down to [m - 1, n - 1]\n",
    "        * when we reach a cell we've seen and we return memo[r][c], that value represents the path from [0, 0] to [r, c] which is not what we want\n",
    "        * we actually want the min path sum of [m - 1, n - 1] to [r, c]\n",
    "        * therefore, when we reach grid[m - 1][n - 1] we actually return its value and not a sum\n",
    "        * essentially we start counting back up when we reach grid[m - 1][n - 1] instead of counting along the way\n",
    "        * we still keep OoB condition the same but we return memo[0][0]\n",
    "* bottom-up dp:\n",
    "    - looking at the grid, we notice that we can calculate the sums of the top row and left columns already since we know that dp[0][0] = grid[0][0]\n",
    "        * we just need to create a dp table and fill those out\n",
    "    - looking at the naive algorithm, we come up with this __recurrence relation__:\n",
    "        - __dp[r][c] = grid[r][c] + Math.min(dp[r - 1][c] + dp[r][c - 1])__\n",
    "    - now why did we do [r - 1] and [c - 1] instead of addition?\n",
    "        * reason being, we can calculate those earlier values already and use them to calculate the next ones\n",
    "    - similar to our naive algorithm, we calculate our sum as we go along from [0, 0] to [m - 1, n - 1]\n",
    "    - since we've already calculated the top row and left column, we can just create 2 for loops that loop from:\n",
    "        - r: 1...m - 1\n",
    "        - c: 1 ... n - 1\n",
    "    - then we return dp[m - 1][n - 1] b/c that is the minimum path sum from [0,0] ... [m - 1,n - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "d07916a3",
   "metadata": {},
   "outputs": [],
   "source": [
    "/**\n",
    " * @param {number[][]} grid\n",
    " * @return {number}\n",
    " */\n",
    "\n",
    " // naive solution\n",
    "var minPathSum = function(grid) {\n",
    "    const numRows = grid.length;\n",
    "    const numCols = grid[0].length;\n",
    "\n",
    "    const traverse = (r, c, sum) => {\n",
    "        // if we are OoB\n",
    "        if ((r < 0 || r >= numRows) ||\n",
    "            (c < 0 || c >= numCols)) {\n",
    "                return Number.POSITIVE_INFINITY;\n",
    "        }\n",
    "\n",
    "        sum += grid[r][c];\n",
    "        if ((r === numRows - 1) && (c === numCols - 1)) {\n",
    "            return sum;\n",
    "        }\n",
    "\n",
    "        return Math.min(traverse(r + 1, c, sum), traverse(r, c + 1, sum));\n",
    "    }\n",
    "\n",
    "    return traverse(0, 0, 0);\n",
    "};\n",
    "\n",
    "// topdown memo\n",
    "var minPathSum = function(grid) {\n",
    "    const numRows = grid.length;\n",
    "    const numCols = grid[0].length;\n",
    "    if (numRows === 1 && numCols === 1) return grid[0][0];\n",
    "    const memo = Array.from({ length: numRows}, () => []);\n",
    "\n",
    "    const traverse = (r, c) => {\n",
    "        // if we are OoB\n",
    "        if ((r < 0 || r >= numRows) ||\n",
    "            (c < 0 || c >= numCols)) {\n",
    "                return Number.POSITIVE_INFINITY;\n",
    "        }\n",
    "\n",
    "        if ((r === numRows - 1) && (c === numCols - 1)) {\n",
    "            return grid[r][c];\n",
    "        }\n",
    "\n",
    "        if (memo[r][c] !== undefined) {\n",
    "            return memo[r][c];\n",
    "        }\n",
    "\n",
    "        memo[r][c] = grid[r][c] + Math.min(traverse(r + 1, c), traverse(r, c + 1));\n",
    "        return memo[r][c];\n",
    "    }\n",
    "\n",
    "    traverse(0, 0);\n",
    "    return memo[0][0];\n",
    "};\n",
    "\n",
    "// bottom-up dp\n",
    "var minPathSum1 = function(grid) {\n",
    "    const numRows = grid.length;\n",
    "    const numCols = grid[0].length;\n",
    "    const dp = Array.from({ length: numRows }, () => []);\n",
    "    dp[0][0] = grid[0][0];\n",
    "\n",
    "    // prefill top row\n",
    "    for (let c = 1; c < numCols; c++) {\n",
    "        dp[0][c] = grid[0][c] + dp[0][c - 1];\n",
    "    }\n",
    "\n",
    "    // prefill left col\n",
    "    for (let r = 1; r < numRows; r++) {\n",
    "        dp[r][0] = grid[r][0] + dp[r - 1][0];\n",
    "    }\n",
    "\n",
    "    for (let r = 1; r < numRows; r++) {\n",
    "        for (let c = 1; c < numCols; c++) {\n",
    "            dp[r][c] = grid[r][c] + Math.min(dp[r - 1][c], dp[r][c - 1]);\n",
    "        }\n",
    "    }\n",
    "\n",
    "    return dp[numRows - 1][numCols - 1];\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "62340046",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "113eea61",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d1d1f323",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "1564092b",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "e81a8333",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "73462cd3",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "f3516700",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "7952d8e8",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "JavaScript (Node.js)",
   "language": "javascript",
   "name": "javascript"
  },
  "language_info": {
   "file_extension": ".js",
   "mimetype": "application/javascript",
   "name": "javascript",
   "version": "16.14.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}