recursion/matrix_maximum_coins.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Problem \n",
    "You are given a 2-d matrix where each cell represents number of coins in that cell. Assuming we start at matrix[0][0], and can only move right or down, find the maximum number of coins you can collect by the bottom right corner.\n",
    "\n",
    "For example, in this matrix\n",
    "\n",
    "```python\n",
    "0 3 1 1\n",
    "2 0 0 4\n",
    "1 5 3 1\n",
    "```\n",
    "\n",
    "The most we can collect is 0 + 2 + 1 + 5 + 3 + 1 = 12 coins."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Approach\n",
    "Consider the following matrix,\n",
    "\n",
    "```\n",
    "0 2 3\n",
    "5 4 9\n",
    "6 7 1\n",
    "```\n",
    "\n",
    "- If we are at 1, the most coins we can collect is ` 1 `\n",
    "- If we start at 7, the most coins we'll co is `7 + 1`\n",
    "- If we start at 9, the most coins we can have is `9 + 1`\n",
    "- If we start at 4, the most coins we can collect is `max(7 + 1,  9 + 1)`\n",
    "\n",
    "This is a recursive problem. \n",
    "\n",
    "The base case will be when we get to the bottom-right corner of the matrix – the most amount of coins we can collect at that point is that cell.\n",
    "This leads to the following solution:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "def collect_coins(matrix, r=0, c=0, cache=None):\n",
    "    if cache is None:\n",
    "        cache = {}\n",
    "    \n",
    "    is_bottom = (r == len(matrix) - 1)\n",
    "    is_rightmost = (c == len(matrix[0]) - 1)\n",
    "    \n",
    "    if (r, c) not in cache:\n",
    "        if is_bottom and is_rightmost:\n",
    "            cache[r, c] = matrix[r][c]\n",
    "        elif is_bottom:\n",
    "            cache[r, c] = matrix[r][c] + collect_coins(matrix, r, c + 1, cache)\n",
    "        elif is_rightmost:\n",
    "            cache[r, c] = matrix[r][c] + collect_coins(matrix, r + 1, c, cache)\n",
    "        else:\n",
    "            cache[r, c] = matrix[r][c] + max(collect_coins(matrix, r, c + 1, cache), collect_coins(matrix, r + 1, c, cache))\n",
    "    return cache[r, c]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": [
       "12"
      ]
     },
     "metadata": {},
     "execution_count": 3
    }
   ],
   "source": [
    "matrix = [\n",
    "  [0, 3, 1, 1],\n",
    "  [2, 0, 0, 4],\n",
    "  [1, 5, 3, 1]\n",
    "]\n",
    "collect_coins(matrix)"
   ]
  }
 ],
 "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.6-final"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}