Dynamic Programming.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Example 1. Independent sets"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given a path graph $G=(V,E)$ with nonnegative weights on vertices. Find the subset of nonadjacent vertices--an independent set--of maximum total weight."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution: Given the maximum total weight up to index i. We consider what property it should have? Obviously we have two choices at index i: include $v_i$ or not include $v_i$:\n",
    "\n",
    "1. Include $v_i$: \n",
    "\n",
    "maximum_total_weight[i]=maximum_total_weight[i-2]+v[i]\n",
    "\n",
    "2. Not include $v_i$:\n",
    "\n",
    "maximum_total_weight[i]=maximum_total_weight[i-1]\n",
    "\n",
    "Then we consider the base case:\n",
    "\n",
    "maximum_total_weight[0]=v[0]\n",
    "\n",
    "maximum_total_weight[1]=max(v[1],v[0])\n",
    "\n",
    "In this way, we can output the maximum total weight. How do we output the optimal solution? We could do a backtracking from index i:\n",
    "\n",
    "1. maximum_total_weight[i]=maximum_total_weight[i-1]: i-=1\n",
    "\n",
    "2. maximum_total_weight[i]=maximum_total_weight[i-2]+v[i]: include v[i] in the solution set; i-=2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def independentSets(nums):\n",
    "    \"\"\"\n",
    "    :type nums: List[int]\n",
    "    :rtype: (int, List[int])(maximum_total_weight, optimal_solution)\n",
    "    \"\"\"\n",
    "    n=len(nums)\n",
    "    if n==0:\n",
    "        return (0,[])\n",
    "    maximum_total_weight=[0]*n\n",
    "    # initialize\n",
    "    maximum_total_weight[0]=nums[0]\n",
    "    if n==1:\n",
    "        return (nums[0],[nums[0]])\n",
    "    maximum_total_weight[1]=max(nums[0],nums[1])\n",
    "    # bottom-up DP\n",
    "    for i in xrange(2,n):\n",
    "        maximum_total_weight[i]=max(maximum_total_weight[i-1],maximum_total_weight[i-2]+nums[i])\n",
    "    # backtrack\n",
    "    optimal_solution=[]\n",
    "    i=n-1\n",
    "    while i>=2:\n",
    "        if maximum_total_weight[i]==maximum_total_weight[i-1]:\n",
    "            i-=1\n",
    "        else:\n",
    "            optimal_solution.append(nums[i])\n",
    "            i-=2\n",
    "    if i==1:\n",
    "        optimal_solution.append(maximum_total_weight[1])\n",
    "    else:\n",
    "        optimal_solution.append(maximum_total_weight[0])\n",
    "        \n",
    "    return (maximum_total_weight[n-1],optimal_solution)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(3, [3])"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nums=[3]\n",
    "independentSets(nums)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Example 2. Knapsack problem"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given n items. Each has a value:\n",
    "\n",
    "* Value $v_i$ (nonnegative)\n",
    "* Size $w_i$ (nonnegative and integral)\n",
    "* Capacity W(a nonnegative integer)\n",
    "\n",
    "Find the subset $S \\subseteq \\{1,2,...,n\\}$ that maximizes $\\sum_{i \\in S}v_i$ subject to $\\sum_{i \\in S}w_i \\leq W$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution: This time the optimal solution will include two values: total_value and total_weight. Suppose we are given an optimal solution at index i, the optimal solution should have the following property: Given the maximal_value with respect to a given capacity at index i, how could we relate it to index i-1?\n",
    "\n",
    "Case 1. i not in the solution set:\n",
    "\n",
    "maximal_value[i,weight]=maximal_value[i-1,weight]\n",
    "\n",
    "Case 2. i in the solution set:\n",
    "\n",
    "maximal_value[i,weight]=maximal_value[i-1,weight-w[i]]+v[i] if weight>=w[i]\n",
    "\n",
    "One edge case here is if w[i]>weight, then \n",
    "\n",
    "maximal_value[i,weight]=maximal_value[i-1,weight]\n",
    "\n",
    "Then we have to figure out the base case to trigger the recursion:\n",
    "\n",
    "maximal_value[0,weight]=v[0] if weight>v[0] else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def knapsack(nums,w):\n",
    "    \"\"\"\n",
    "    :type nums: List[(int(value),int(weight))]\n",
    "    :type w: int\n",
    "    :rtype: (int, List[int])(maximum_total_value, optimal_solution)\n",
    "    \"\"\"\n",
    "    n=len(nums)\n",
    "    if n==0: return 0\n",
    "    maximal_value=[[0]*(w+1) for i in xrange(n)]\n",
    "    for weight in xrange(w+1):\n",
    "        if weight>=nums[0][1]:\n",
    "            maximal_value[0][weight]=nums[0][0]\n",
    "            \n",
    "    for i in xrange(1,n):\n",
    "        for j in xrange(w+1):\n",
    "            if j>=nums[i][1]:\n",
    "                maximal_value[i][j]=max(maximal_value[i-1][j],maximal_value[i-1][j-nums[i][1]]+nums[i][0])\n",
    "            else:\n",
    "                maximal_value[i][j]=maximal_value[i-1][j]\n",
    "    return maximal_value[n-1][w]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "8"
      ]
     },
     "execution_count": 41,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nums=[(3,4),(2,3),(4,2),(4,3)]\n",
    "knapsack(nums,6)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Then we output optimal solution by backtracking: if maximal_value[i][j]!=maximal_value[i-1][j]: include i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 77,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def knapsack(nums,w):\n",
    "    \"\"\"\n",
    "    :type nums: List[(int(value),int(weight))]\n",
    "    :type w: int\n",
    "    :rtype: (int, List[int])(maximum_total_value, optimal_solution)\n",
    "    \"\"\"\n",
    "    n=len(nums)\n",
    "    if n==0: return (0,[])\n",
    "    maximal_value=[[0]*(w+1) for i in xrange(n+1)]\n",
    "            \n",
    "    for i in xrange(1,n+1):\n",
    "        for j in xrange(w+1):\n",
    "            if j>=nums[i-1][1]:\n",
    "                maximal_value[i][j]=max(maximal_value[i-1][j],maximal_value[i-1][j-nums[i-1][1]]+nums[i-1][0])\n",
    "            else:\n",
    "                maximal_value[i][j]=maximal_value[i-1][j]\n",
    "                \n",
    "    optimal_solution=[]\n",
    "    j=w\n",
    "    for i in xrange(n,0,-1):\n",
    "        if maximal_value[i][j]!=maximal_value[i-1][j]:\n",
    "            optimal_solution.append(i)\n",
    "            j-=nums[i-1][1]\n",
    "\n",
    "    return (maximal_value[n][w],optimal_solution)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 80,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(5, [1])"
      ]
     },
     "execution_count": 80,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nums=[(5,6),(1,1)]\n",
    "knapsack(nums,6)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Example 3. Sequence alignment "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given X=x_1...x_m and Y=y_1...y_n over some alphabet $\\Sigma$ and penalty $\\alpha_{gap}$ for inserting a gap and $\\alpha_{a b}$ for matching a and b[if a==b $\\alpha_{a b}=0$]. Find alignment with minimum possible total penalty."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution: Suppose X and Y are already aligned at the index i, then how can we deduce i-1? First we consider the cases at index i:\n",
    "\n",
    "1. x_m and y_n exist\n",
    "2. x_m matches a gap\n",
    "3. y_n matches a gap\n",
    "\n",
    "min_penalty[i,j]=min(min_penalty[i-1,j-1]+alpha_m n, min_penalty[i-1,j]+alpha_gap, min_penalty[i,j-1]+alpha_gap), i=1,...m, j=1,...,n\n",
    "\n",
    "Then we consider the base case:\n",
    "\n",
    "min_penalty[i,0]=i*alpha_gap\n",
    "\n",
    "min_penalty[0,j]=j*alpha_gap"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def sequenceAlignment(x, y, alpha_gap, alpha_mismatch):\n",
    "    \"\"\"\n",
    "    :type x,y: str\n",
    "    :type alpha_gap, alpha_mismatch: int\n",
    "    :rtype: int\n",
    "    \"\"\"\n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Example 4. Optimal binary search trees"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Input: Frequencies $p_1, p_2, ..., p_n$ for items 1,2,...,n (Assume items in sorted order, $1<2<...<n$)\n",
    "\n",
    "Goal: Compute a valid search tree that minimizes the weighted (average) search time.\n",
    "\n",
    "C(T)=\\sum_i p_i * (search time for i in T = depth of i in T+1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 62. Unique Paths"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).\n",
    "\n",
    "The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).\n",
    "\n",
    "How many possible unique paths are there?\n",
    "\n",
    "<img src=http://leetcode.com/wp-content/uploads/2014/12/robot_maze.png>\n",
    "\n",
    "Note: m and n will be at most 100."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution: Recursive solution:\n",
    "\n",
    "number of paths starting at (i,j)=number of paths starting at (i+1,j)+number of paths starting at (i,j+1)\n",
    "\n",
    "We could build the solution from bottom-up. \n",
    "$$\n",
    "number of paths at (m,n)=1 \\\\\n",
    "number of pahs at (m,n-1)=1 \\\\\n",
    "number of pahs at (m,n-2)=1 \\\\\n",
    "... \\\\\n",
    "number of pahs at (m,1)=1 \\\\\n",
    "number of pahs at (m-1,n)=1\\\\\n",
    "number of pahs at (m-1,n-1)=1\\\\\n",
    "...\n",
    "\n",
    "$$\n",
    "\n",
    "The time complexity will be O(m n) and the space complexity will be O(m n)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def uniquePaths(self, m, n):\n",
    "        \"\"\"\n",
    "        :type m: int\n",
    "        :type n: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        num_paths=[[0]*(n+1) for i in range(m+1)]\n",
    "        num_paths[m-1][n]=1\n",
    "        for i in range(m)[::-1]:\n",
    "            for j in range(n)[::-1]:\n",
    "                num_paths[i][j]=num_paths[i+1][j]+num_paths[i][j+1]\n",
    "        return num_paths[0][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 64,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 64,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "o=Solution()\n",
    "o.uniquePaths(2,3) "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 63. Unique Paths II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Follow up for \"Unique Paths\":\n",
    "\n",
    "Now consider if some obstacles are added to the grids. How many unique paths would there be?\n",
    "\n",
    "An obstacle and empty space is marked as 1 and 0 respectively in the grid.\n",
    "\n",
    "For example,\n",
    "There is one obstacle in the middle of a 3x3 grid as illustrated below.\n",
    "\n",
    "[\n",
    "  [0,0,0],\n",
    "  [0,1,0],\n",
    "  [0,0,0]\n",
    "]\n",
    "\n",
    "The total number of unique paths is 2.\n",
    "\n",
    "Note: m and n will be at most 100."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 77,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def uniquePathsWithObstacles(self, obstacleGrid):\n",
    "        \"\"\"\n",
    "        :type obstacleGrid: List[List[int]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if len(obstacleGrid)==0 or len(obstacleGrid[0])==0:\n",
    "            return 0\n",
    "        m=len(obstacleGrid)\n",
    "        n=len(obstacleGrid[0])\n",
    "        num_paths=[[0]*(n+1) for i in range(m+1)]\n",
    "        num_paths[1][0]=1\n",
    "        for i in range(1,m+1):\n",
    "            for j in range(1,n+1):\n",
    "                if obstacleGrid[i-1][j-1]==1:\n",
    "                    num_paths[i][j]=0\n",
    "                else:\n",
    "                    num_paths[i][j]=num_paths[i-1][j]+num_paths[i][j-1]\n",
    "        return num_paths[m][n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 79,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 79,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "o=Solution()\n",
    "obstacleGrid=[[0,0,0],[1,0,0],[0,0,0]]\n",
    "o.uniquePathsWithObstacles(obstacleGrid) "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 70. Climbing Stairs"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You are climbing a stair case. It takes n steps to reach to the top.\n",
    "\n",
    "Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution: \n",
    "\n",
    "$$\n",
    "ways to get step i=ways to get step (i-1)+ways to get step (i-2) \\\\\n",
    "...\\\\\n",
    "ways to get step 3=2+1\\\\\n",
    "ways to get step 2=1+1\\\\\n",
    "ways to get step 1=1\\\\\n",
    "ways to get step 0=1\\\\\n",
    "$$\n",
    "\n",
    "Obviously, ways to get step i depends on ways to get step (i-1) and step (i-2). We can solve the problem from bottom-up."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def climbStairs(self, n):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        ways=[0]*(n+1)\n",
    "        ways[0]=1\n",
    "        ways[1]=1\n",
    "        for i in range(2,n+1):\n",
    "            ways[i]=ways[i-1]+ways[i-2]\n",
    "            \n",
    "        return ways[-1]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 91. Decode Ways"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A message containing letters from A-Z is being encoded to numbers using the following mapping:\n",
    "\n",
    "'A' -> 1\n",
    "\n",
    "'B' -> 2\n",
    "\n",
    "...\n",
    "\n",
    "'Z' -> 26\n",
    "\n",
    "Given an encoded message containing digits, determine the total number of ways to decode it.\n",
    "\n",
    "For example,\n",
    "Given encoded message \"12\", it could be decoded as \"AB\" (1 2) or \"L\" (12).\n",
    "\n",
    "The number of ways decoding \"12\" is 2."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution: We consider the number of ways decoding message upto index i:\n",
    "\n",
    "if s[i-1]=='0' and s[i]=='0':\n",
    "     return 0\n",
    "elif s[i-1]!='0' and s[i]=='0':\n",
    "     if int(s[i-1:i+1])<=26:\n",
    "       if i>=2: \n",
    "         count[i]=count[i-2]\n",
    "       else:\n",
    "         count[i]=1\n",
    "     else:\n",
    "        return 0\n",
    "elif s[i-1]=='0' and s[i]!='0':\n",
    "     count[i]=count[i-1]\n",
    "else:\n",
    "    if int(s[i-1:i+1])<=26:\n",
    "       count[i]=count[i-2]+count[i-1]\n",
    "    else:\n",
    "       count[i]=count[i-2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 83,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def numDecodings(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        n=len(s)\n",
    "        if n==0: return 0\n",
    "        count=[0]*n\n",
    "        count[0]=int(s[0]!='0')\n",
    "        for i in xrange(1,n):\n",
    "            if s[i-1]=='0' and s[i]=='0':\n",
    "                return 0\n",
    "            elif s[i-1]!='0' and s[i]=='0':\n",
    "                if int(s[i-1:i+1])<=26:\n",
    "                    if i>=2:\n",
    "                        count[i]=count[i-2]\n",
    "                    else:\n",
    "                        count[i]=1\n",
    "                else:\n",
    "                    return 0\n",
    "            elif s[i-1]=='0' and s[i]!='0':\n",
    "                count[i]=count[i-1]\n",
    "            else:\n",
    "                if int(s[i-1:i+1])<=26:\n",
    "                    if i>=2:\n",
    "                        count[i]=count[i-2]+count[i-1]\n",
    "                    else:\n",
    "                        count[i]=1+count[i-1]\n",
    "                else:\n",
    "                    count[i]=count[i-1]\n",
    "                        \n",
    "        return count[n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 84,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 2, 2]\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 84,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "o=Solution()\n",
    "s=\"227\"\n",
    "o.numDecodings(s)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 96. Unique Binary Search Trees"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given n, how many structurally unique BST's (binary search trees) that store values 1...n?\n",
    "\n",
    "For example,\n",
    "Given n = 3, there are a total of 5 unique BST's.\n",
    "\n",
    " 1         3     3      2      1\n",
    "    \\       /     /      / \\      \\\n",
    "     3     2     1      1   3      2\n",
    "    /     /       \\                 \\\n",
    "   2     1         2                 3\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution: By observation, root node can take value from 1 to n, e.g. root=i. Then the left subtree is constructed from 1 to i-1; the right subtree is constructed from i+1 to n. So we have the following recursion relation:\n",
    "\n",
    "$$\n",
    "numBST(1,n) = \\sum_{i=1}^{n} (numBST(1,i-1)*numBST(i+1,n))\n",
    "$$\n",
    "\n",
    "The second observation is\n",
    "\n",
    "$$\n",
    "numBST(i+1,n)=numBST(1,n-i)\n",
    "$$\n",
    "\n",
    "In other words, the number of unique BST only depends on the length of the input consecutive numbers. So our recursion relation can be simplified as\n",
    "$$\n",
    "numBST(n) = \\sum_{i=1}^{n} (numBST(i-1)*numBST(n-i))\n",
    "$$\n",
    "\n",
    "Specifically,\n",
    "$$\n",
    "numBST(0)=1\n",
    "numBST(1)=1 \\\\\n",
    "numBST(2)=numBST(1)*numBST(0)+numBST(0)*numBST(1) \\\\\n",
    "numBST(3)=numBST(2)*numBST(0)+numBST(1)*numBST(1)+numBST(0)*numBST(2) \\\\\n",
    "... \\\\\n",
    "$$\n",
    "\n",
    "The time complexity for this solution will be O(n^2). The space complexity will be O(n). Can we do better?\n",
    "$$\n",
    "numBST(0)=1 \\\\\n",
    "numBST(1)=1 \\\\\n",
    "numBST(2)=numBST(1)*numBST(0)+numBST(0)*numBST(1) \\\\\n",
    "numBST(3)=numBST(2)*numBST(0)+numBST(1)*numBST(1)+numBST(0)*numBST(2) \\\\\n",
    "numBST(4)=numBST(3)*numBST(0)+numBST(2)*numBST(1)+numBST(1)*numBST(2)+numBST(0)*numBST(3) \\\\\n",
    "... \\\\\n",
    "$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 80,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def numTrees(self, n):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        # summation[n]=sum_i=1^n numBST(i)\n",
    "        numBST=[0]*(n+1)       \n",
    "        if n==1:\n",
    "            return 1\n",
    "        numBST[0]=1\n",
    "        numBST[1]=1\n",
    "        for i in range(2,n+1):\n",
    "            numBST[i]=0\n",
    "            for j in range(i):\n",
    "                numBST[i]+=numBST[j]*numBST[i-1-j]\n",
    "        return numBST[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 82,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 82,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "o=Solution()\n",
    "o.numTrees(2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 95. Unique Binary Search Trees II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given an integer n, generate all structurally unique BST's (binary search trees) that store values 1...n.\n",
    "\n",
    "For example,\n",
    "Given n = 3, your program should return all 5 unique BST's shown below.\n",
    "\n",
    "   1         3     3      2      1\n",
    "    \\       /     /      / \\      \\\n",
    "     3     2     1      1   3      2\n",
    "    /     /       \\                 \\\n",
    "   2     1         2                 3\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution: First we pick up a number for the root, then we construct the left and right subtrees by recursion. The difficulty lies in how to construct these trees without mess up the nodes. We have to make a deep copy of the whole tree structure when tracing the child nodes. It turns out to be much easier to do it bottom up as we could store the subtrees before reaching the parent nodes as the number of copies of parent nodes depend on the number of its subtrees. So we come up with a DP bottom-up solution."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 88,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution(object):\n",
    "    def generateTrees(self, n):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :rtype: List[TreeNode]\n",
    "        \"\"\"\n",
    "        return self._generateTrees(1,n)\n",
    "        \n",
    "    def _generateTrees(self,nmin,nmax):\n",
    "        heads=[]\n",
    "        if nmin>nmax:\n",
    "            return [None]\n",
    "        for i in range(nmin, nmax+1):\n",
    "            for left in self._generateTrees(nmin,i-1):\n",
    "                for right in self._generateTrees(i+1,nmax):\n",
    "                    root=TreeNode(i)\n",
    "                    root.left=left\n",
    "                    root.right=right\n",
    "                    heads.append(root)\n",
    "        return heads"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 89,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[None]"
      ]
     },
     "execution_count": 89,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "o=Solution()\n",
    "o.generateTrees(0)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 123. <font color=red>Best Time to Buy and Sell Stock III"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Say you have an array for which the ith element is the price of a given stock on day i.\n",
    "\n",
    "Design an algorithm to find the maximum profit. You may complete at most two transactions.\n",
    "\n",
    "Note:\n",
    "You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution: One solution is to find all the increasing part and sort them, then we sum the largest two values. In the worst case, the time complexity will be O(n log n), the space complexity will be O(n). To improve, we could use max and second max to keep track of the two most profitable transactions. The problem should be solved in one pass."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def maxProfit(self, prices):\n",
    "        \"\"\"\n",
    "        :type prices: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        max_profit=0\n",
    "        second_max_profit=0\n",
    "        profit=0\n",
    "        n=len(prices)\n",
    "        for i in range(1,n):\n",
    "            if prices[i]>prices[i-1]:\n",
    "                profit+=prices[i]-prices[i-1]\n",
    "            else:\n",
    "                if profit>max_profit:\n",
    "                    second_max_profit=max_profit\n",
    "                    max_profit=profit\n",
    "                elif profit>second_max_profit:\n",
    "                    second_max_profit=profit\n",
    "                profit=0\n",
    "        # check last increasing transaction\n",
    "        if profit>max_profit:\n",
    "            second_max_profit=max_profit\n",
    "            max_profit=profit\n",
    "        elif profit>second_max_profit:\n",
    "            second_max_profit=profit               \n",
    "                \n",
    "        return max_profit+second_max_profit"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The above solution is not right if we consider the case [1,2,4,2,5,7,2,4,9,0] as we do not have to sell the stock when it is decreasing. We could do a forward pass for the first transaction and a backward pass for the second transaction, then we notice that the second transaction must be after the first. We can pick up the max profit for profit1[i]+profit2[i], i=0,...,n-1. The time complexity will be O(n), the space complexity will be O(n)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 103,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import sys\n",
    "\n",
    "class Solution(object):\n",
    "    def maxProfit(self, prices):\n",
    "        \"\"\"\n",
    "        :type prices: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        n=len(prices)\n",
    "        if n<=1:\n",
    "            return 0\n",
    "        first_profit=[0]*n\n",
    "        second_profit=[0]*n\n",
    "        # forward pass\n",
    "        buy=False\n",
    "        max_profit=0\n",
    "        buy_price=sys.maxint\n",
    "        sell_price=0\n",
    "        for i in range(n):\n",
    "            if prices[i]<buy_price:\n",
    "                buy=True\n",
    "                buy_price=prices[i]\n",
    "            if buy:\n",
    "                sell_price=prices[i]\n",
    "            if sell_price-buy_price>max_profit:\n",
    "                max_profit=sell_price-buy_price\n",
    "            first_profit[i]=max_profit\n",
    "        # backward pass\n",
    "        sell=False\n",
    "        max_profit=0\n",
    "        sell_price=-sys.maxint\n",
    "        buy_price=0\n",
    "        for i in range(n)[::-1]:\n",
    "            if prices[i]>sell_price:\n",
    "                sell=True\n",
    "                sell_price=prices[i]\n",
    "            if sell:\n",
    "                buy_price=prices[i]\n",
    "            if sell_price-buy_price>max_profit:\n",
    "                max_profit=sell_price-buy_price\n",
    "            second_profit[i]=max_profit\n",
    "        return max([transaction1+transaction2 for (transaction1,transaction2) in zip(first_profit,second_profit)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 104,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "13"
      ]
     },
     "execution_count": 104,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "o=Solution()\n",
    "prices=[1,2,4,2,5,7,2,4,9,0]\n",
    "o.maxProfit(prices)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<font color=red>There turns out to be a better solution based on mathematics. I will refer to it later."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## <font color=red>139. Word Break"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words. You may assume the dictionary does not contain duplicate words.\n",
    "\n",
    "For example, given\n",
    "s = \"leetcode\",\n",
    "dict = [\"leet\", \"code\"].\n",
    "\n",
    "Return true because \"leetcode\" can be segmented as \"leet code\".\n",
    "\n",
    "UPDATE (2017/1/4):\n",
    "\n",
    "The wordDict parameter had been changed to a list of strings (instead of a set of strings). Please reload the code definition to get the latest changes.\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def wordBreak(self, s, wordDict):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :type wordDict: List[str]\n",
    "        :rtype: bool\n",
    "        \"\"\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## <font color=red>140. Word Break II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, add spaces in s to construct a sentence where each word is a valid dictionary word. You may assume the dictionary does not contain duplicate words.\n",
    "\n",
    "Return all such possible sentences.\n",
    "\n",
    "For example, given\n",
    "\n",
    "s = \"catsanddog\",\n",
    "\n",
    "dict = [\"cat\", \"cats\", \"and\", \"sand\", \"dog\"].\n",
    "\n",
    "A solution is [\"cats and dog\", \"cat sand dog\"].\n",
    "\n",
    "UPDATE (2017/1/4):\n",
    "\n",
    "The wordDict parameter had been changed to a list of strings (instead of a set of strings). Please reload the code definition to get the latest changes."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def wordBreak(self, s, wordDict):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :type wordDict: List[str]\n",
    "        :rtype: List[str]\n",
    "        \"\"\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 198. House Robber"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.\n",
    "\n",
    "Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution: Discussion solution: \n",
    "\n",
    "$$\n",
    "f(0) = nums[0] \\\\\n",
    "f(1) = max(num[0], num[1]) \\\\\n",
    "f(k) = max( f(k-2) + nums[k], f(k-1) ) \\\\\n",
    "$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def rob(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        n=len(nums)\n",
    "        if n==0:\n",
    "            return 0\n",
    "        max_kminus1=0\n",
    "        max_kminus2=0\n",
    "        max_k=0\n",
    "        for i in range(n):\n",
    "            max_k=max(max_kminus2+nums[i],max_kminus1)\n",
    "            max_kminus2=max_kminus1\n",
    "            max_kminus1=max_k\n",
    "        return max_k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "o=Solution()\n",
    "o.rob([1,1])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For the k-th house, it is either robbed or not robbed, if k-th house is not robbed, then we need the maximum between the maximum of k-1-th house robbed and the maximum of k-1th not robbed; If k-th house is robbed， then we need the maximum of k-1-th house not robbed. Thus we have\n",
    "\n",
    "$$\n",
    "f(k) = max( include\\ k\\ maximum, exclude\\ k\\ maximum ) \\\\\n",
    "include\\ k\\ maximum=exclude\\ k-1\\ maximum + nums[k] \\\\\n",
    "exclude\\ k\\ maximum=max( include\\ k-1\\ maximum, exclude\\ k-1\\ maximum )=f(k-1)\n",
    "$$\n",
    "\n",
    "which is equivalent to\n",
    "\n",
    "$$\n",
    "f(k) = max( exclude\\ k-1\\ maximum+nums[k], f(k-1) ) \\\\\n",
    "=max( f(k-2)+nums[k], f(k-1) )\n",
    "$$\n",
    "\n",
    "The initial condition is \n",
    "\n",
    "$$\n",
    "f(0)=nums[0] \\\\\n",
    "f(1)=max(nums[1],nums[0]) \\\\\n",
    "...\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 213. House Robber II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Note: This is an extension of House Robber.\n",
    "\n",
    "After robbing those houses on that street, the thief has found himself a new place for his thievery so that he will not get too much attention. This time, all houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, the security system for these houses remain the same as for those in the previous street.\n",
    "\n",
    "Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution: As it is an extention of House Robber I, we expect to make use of the solution to House Robber. Consider \n",
    "\n",
    "1. house i not robbed, maximum of the chain i+1 to i-1\n",
    "2. house i robbed, maximum of the chain i+2 to i-2\n",
    "3. iterate over i to find max\n",
    "\n",
    "time complexity O(n^2). Can we simplify it? Notice that house i robbed is included in house i+1 not robbed and we only need to pick up one i to cover all the cases. we can pick up 0 and 0+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def rob(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        n=len(nums)\n",
    "        if n==1:\n",
    "            return nums[0]\n",
    "        return max(self._rob(nums[1:n]),self._rob(nums[0:n-1]))\n",
    "        \n",
    "    def _rob(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        n=len(nums)\n",
    "        if n==0:\n",
    "            return 0\n",
    "        max_kminus1=0\n",
    "        max_kminus2=0\n",
    "        max_k=0\n",
    "        for i in range(n):\n",
    "            max_k=max(max_kminus2+nums[i],max_kminus1)\n",
    "            max_kminus2=max_kminus1\n",
    "            max_kminus1=max_k\n",
    "        return max_k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "o=Solution()\n",
    "o.rob([1,1,2,1,3])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 221. Maximal Square"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given a 2D binary matrix filled with 0's and 1's, find the largest square containing only 1's and return its area.\n",
    "\n",
    "For example, given the following matrix:\n",
    "\n",
    "1 0 1 0 0\n",
    "\n",
    "1 0 1 1 1\n",
    "\n",
    "1 1 1 1 1\n",
    "\n",
    "1 0 0 1 0\n",
    "\n",
    "Return 4.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution: Brutal force: start from every position that is 1 and expand it to maximum area containing only 1's. Time complexity O(n^4). Consider alternative DP solution: Let the maximum size(size^2=area) of the square that can be achieved at (i, j)(which is the bottom-right corner of the square) denoted by $P[i][j]$. Then\n",
    "\n",
    "1. If matrix[i][j]==0: P[i][j]=0\n",
    "2. If matrix[i][j]==1: P[i][j]=min(P[i-1][j],P[i-1][j-1],P[i][j-1])+1\n",
    "\n",
    "Base case:\n",
    "\n",
    "P[0][j]=matrix[0][j]\n",
    "P[i][0]=matrix[i][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def maximalSquare(self, matrix):\n",
    "        \"\"\"\n",
    "        :type matrix: List[List[str]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        m=len(matrix)\n",
    "        if m==0: return 0\n",
    "        n=len(matrix[0])\n",
    "        if n==0: return 0\n",
    "        size=[[0]*n for i in xrange(m)]\n",
    "        sizemax=0\n",
    "        # base case\n",
    "        for i in xrange(m):\n",
    "            size[i][0]=int(matrix[i][0])\n",
    "            sizemax=max(size[i][0],sizemax)\n",
    "        for j in xrange(n):\n",
    "            size[0][j]=int(matrix[0][j])\n",
    "            sizemax=max(size[0][j],sizemax)\n",
    "        # DP\n",
    "        for i in xrange(1,m):\n",
    "            for j in xrange(1,n):\n",
    "                size[i][j]=min(size[i-1][j],size[i][j-1],size[i-1][j-1])+1 if matrix[i][j]=='1' else 0\n",
    "                sizemax=max(sizemax,size[i][j])\n",
    "        return sizemax**2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "o=Solution()\n",
    "matrix=[['1','0','1','0','0'],['1','0','1','1','1'],['1','1','1','1','1'],['1','0','0','1','0']]\n",
    "o.maximalSquare(matrix)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 303. Range Sum Query - Immutable"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.\n",
    "\n",
    "Example:\n",
    "Given nums = [-2, 0, 3, -5, 2, -1]\n",
    "\n",
    "sumRange(0, 2) -> 1\n",
    "\n",
    "sumRange(2, 5) -> -1\n",
    "\n",
    "sumRange(0, 5) -> -3\n",
    "\n",
    "Note:\n",
    "\n",
    "1. You may assume that the array does not change.\n",
    "2. There are many calls to sumRange function.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution: By use of the recursion relation,\n",
    "\n",
    "$$\n",
    "sumRange(i,i+d)=sumRange(i,i+d-1)+nums[i+d]\n",
    "$$\n",
    "\n",
    "We could build the sum table in O(n^2)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "But this is not the best solution. We could examine sum(0,k)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class NumArray(object):\n",
    "    def __init__(self, nums):\n",
    "        \"\"\"\n",
    "        initialize your data structure here.\n",
    "        :type nums: List[int]\n",
    "        \"\"\"\n",
    "        n=len(nums)\n",
    "        self.nums=nums\n",
    "        self.sums=[0]*n\n",
    "        if n>0:\n",
    "            self.sums[0]=nums[0]\n",
    "        for i in range(1,n):\n",
    "            self.sums[i]=self.sums[i-1]+nums[i]\n",
    "\n",
    "    def sumRange(self, i, j):\n",
    "        \"\"\"\n",
    "        sum of elements nums[i..j], inclusive.\n",
    "        :type i: int\n",
    "        :type j: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        return self.sums[j]-self.sums[i-1] if i>0 else self.sums[j]\n",
    "\n",
    "\n",
    "# Your NumArray object will be instantiated and called as such:\n",
    "# numArray = NumArray(nums)\n",
    "# numArray.sumRange(0, 1)\n",
    "# numArray.sumRange(1, 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "-1"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nums = [-2, 0, 3, -5, 2, -1]\n",
    "o=NumArray(nums)\n",
    "o.sumRange(2,5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 304. Range Sum Query 2D - Immutable"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given a 2D matrix matrix, find the sum of the elements inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2).\n",
    "\n",
    "<img src=https://leetcode.com/static/images/courses/range_sum_query_2d.png>\n",
    "\n",
    "The above rectangle (with the red border) is defined by (row1, col1) = (2, 1) and (row2, col2) = (4, 3), which contains sum = 8.\n",
    "\n",
    "Example:\n",
    "\n",
    "Given matrix = [\n",
    "  [3, 0, 1, 4, 2],\n",
    "  [5, 6, 3, 2, 1],\n",
    "  [1, 2, 0, 1, 5],\n",
    "  [4, 1, 0, 1, 7],\n",
    "  [1, 0, 3, 0, 5]\n",
    "]\n",
    "\n",
    "sumRegion(2, 1, 4, 3) -> 8\n",
    "\n",
    "sumRegion(1, 1, 2, 2) -> 11\n",
    "\n",
    "sumRegion(1, 2, 2, 4) -> 12\n",
    "\n",
    "Note:\n",
    "1. You may assume that the matrix does not change.\n",
    "2. There are many calls to sumRegion function.\n",
    "3. You may assume that row1 ≤ row2 and col1 ≤ col2.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution: Brutal force: O((row2-row1)*(col2-col1)) in each call. We should be able to solve the problem in O(m*n) time if we use memory O(m*n) in sums(i,j), where each entry stores the patial sum from col 0 to i and row 0 to j. We consider the following recursion:\n",
    "\n",
    "$$\n",
    "sums(i,j)=nums(i,j)+sums(i,j-1)+sums(i-1,j)-sums(i-1,j-1)\n",
    "$$\n",
    "\n",
    "In order to avoid the edge cases manipulation, we could allocate our sums matrix to be (m+1)*(n+1). Bases on sums(i,j), we have\n",
    "\n",
    "$$\n",
    "sumRegion(i_1,j_1,i_2,j_2)=sums(i_2,j_2)-sums(i1-1,j2)-sums(i_2,j_1-1)+sums(i_1-1,j_1-1)\n",
    "$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class NumMatrix(object):\n",
    "    def __init__(self, matrix):\n",
    "        \"\"\"\n",
    "        initialize your data structure here.\n",
    "        :type matrix: List[List[int]]\n",
    "        \"\"\"\n",
    "        self.matrix=matrix\n",
    "        if len(matrix)==0 or len(matrix[0])==0:\n",
    "            return\n",
    "        m=len(matrix)\n",
    "        n=len(matrix[0])\n",
    "        self.sums=[[0]*(n+1) for i in range(m+1)]\n",
    "        for i in range(1,m+1):\n",
    "            for j in range(1,n+1):\n",
    "                self.sums[i][j]=self.matrix[i-1][j-1]+self.sums[i][j-1]+self.sums[i-1][j]-self.sums[i-1][j-1]\n",
    "\n",
    "    def sumRegion(self, row1, col1, row2, col2):\n",
    "        \"\"\"\n",
    "        sum of elements matrix[(row1,col1)..(row2,col2)], inclusive.\n",
    "        :type row1: int\n",
    "        :type col1: int\n",
    "        :type row2: int\n",
    "        :type col2: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        return self.sums[row2+1][col2+1]-self.sums[row1][col2+1]-self.sums[row2+1][col1]+self.sums[row1][col1]\n",
    "\n",
    "\n",
    "# Your NumMatrix object will be instantiated and called as such:\n",
    "# numMatrix = NumMatrix(matrix)\n",
    "# numMatrix.sumRegion(0, 1, 2, 3)\n",
    "# numMatrix.sumRegion(1, 2, 3, 4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 90,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[1, 0, 0], [0, 0, 0], [0, 0, 0]]"
      ]
     },
     "execution_count": 90,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "matrix=[[0]*3 for i in range(3)]\n",
    "matrix[0][0]=1\n",
    "matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 309. Best Time to Buy and Sell Stock with Cooldown"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Say you have an array for which the ith element is the price of a given stock on day i.\n",
    "\n",
    "Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times) with the following restrictions:\n",
    "\n",
    "* You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).\n",
    "* After you sell your stock, you cannot buy stock on next day. (ie, cooldown 1 day)\n",
    "\n",
    "Example:\n",
    "\n",
    "prices = [1, 2, 3, 0, 2]\n",
    "\n",
    "maxProfit = 3\n",
    "\n",
    "transactions = [buy, sell, cooldown, buy, sell]\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution: First we find out all the increasing interval in the stock prices. We record all the index pairs and then check the cool down condition to maximize the profits."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 90,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def maxProfit(self, prices):\n",
    "        \"\"\"\n",
    "        :type prices: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        buy=0\n",
    "        sell=0\n",
    "        n=len(prices)\n",
    "        intervals=[]\n",
    "        for i in xrange(1,n):\n",
    "            if prices[i]-prices[i-1]>0:\n",
    "                sell+=1\n",
    "                if i==n-1:\n",
    "                    intervals.append([buy,sell])\n",
    "            else:\n",
    "                if buy!=sell:\n",
    "                    intervals.append([buy,sell])\n",
    "                buy=sell=i\n",
    "        \n",
    "        profit=0\n",
    "        while intervals!=[]:\n",
    "            curr=intervals.pop()\n",
    "            profit+=prices[curr[1]]-prices[curr[0]]\n",
    "            if intervals!=[] and intervals[-1][1]==curr[0]-1:\n",
    "                profit-=min(prices[curr[0]+1]-prices[curr[0]],prices[intervals[-1][1]]-prices[intervals[-1][1]-1])\n",
    "                \n",
    "        return profit"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 93,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 93,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "prices = [1, 2, 3, 0, 2]\n",
    "o=Solution()\n",
    "o.maxProfit(prices)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The above solution is wrong for [6,1,3,2,4,7], where we have ignore the case that we do not need to sell between the two intervals with 1 day difference."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 94,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5"
      ]
     },
     "execution_count": 94,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "prices = [6,1,3,2,4,7]\n",
    "o=Solution()\n",
    "o.maxProfit(prices)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 95,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def maxProfit(self, prices):\n",
    "        \"\"\"\n",
    "        :type prices: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        buy=0\n",
    "        sell=0\n",
    "        n=len(prices)\n",
    "        intervals=[]\n",
    "        for i in xrange(1,n):\n",
    "            if prices[i]-prices[i-1]>0:\n",
    "                sell+=1\n",
    "                if i==n-1:\n",
    "                    intervals.append([buy,sell])\n",
    "            else:\n",
    "                if buy!=sell:\n",
    "                    intervals.append([buy,sell])\n",
    "                buy=sell=i\n",
    "        \n",
    "        profit=0\n",
    "        while intervals!=[]:\n",
    "            curr=intervals.pop()\n",
    "            profit+=prices[curr[1]]-prices[curr[0]]\n",
    "            if intervals!=[] and intervals[-1][1]==curr[0]-1:\n",
    "                profit-=min(prices[curr[0]+1]-prices[curr[0]],\\\n",
    "                            prices[intervals[-1][1]]-prices[intervals[-1][1]-1],\\\n",
    "                           prices[intervals[-1][1]]-prices[curr[0]])\n",
    "                \n",
    "        return profit"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 96,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "6"
      ]
     },
     "execution_count": 96,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "prices = [6,1,3,2,4,7]\n",
    "o=Solution()\n",
    "o.maxProfit(prices)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The above solution is wrong for [2,6,8,7,8,7,9,4,1,2,4,5,8] as it neglects the modification of buy and sell days when pop from the intervals. It seems that the strategy I take is subtle at this case."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 114,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def maxProfit(self, prices):\n",
    "        \"\"\"\n",
    "        :type prices: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        buy=0\n",
    "        sell=0\n",
    "        n=len(prices)\n",
    "        intervals=[]\n",
    "        for i in xrange(1,n):\n",
    "            if prices[i]-prices[i-1]>0:\n",
    "                sell+=1\n",
    "                if i==n-1:\n",
    "                    intervals.append([buy,sell])\n",
    "            else:\n",
    "                if buy!=sell:\n",
    "                    intervals.append([buy,sell])\n",
    "                buy=sell=i\n",
    "        \n",
    "        profit=0\n",
    "        while intervals!=[]:\n",
    "            curr=intervals.pop()\n",
    "            profit+=prices[curr[1]]-prices[curr[0]]\n",
    "            if intervals!=[] and intervals[-1][1]==curr[0]-1 and intervals[-1][1]>intervals[-1][0]:\n",
    "                diff1=prices[curr[0]+1]-prices[curr[0]]\n",
    "                diff2=prices[intervals[-1][1]]-prices[intervals[-1][1]-1]\n",
    "                diff3=prices[intervals[-1][1]]-prices[curr[0]]\n",
    "                profit-=min(diff1,diff2,diff3)\n",
    "                if diff2<diff1 and diff2<diff3:\n",
    "                    intervals[-1]=[intervals[-1][0],intervals[-1][1]-1]\n",
    "                print curr, intervals[-1]\n",
    "                \n",
    "        return profit"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 115,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[5, 6] [3, 4]\n",
      "[3, 4] [0, 2]\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "14"
      ]
     },
     "execution_count": 115,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "prices = [2,6,8,7,8,7,9,4,1,2,4,5,8]\n",
    "o=Solution()\n",
    "o.maxProfit(prices)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We consider a DP solution for this problem: Suppose we are given the maximum profit at day i, how does it relate to previous days? At day i, we have 4 cases: \n",
    "\n",
    "1. have 0 stock and buy 1<-max_profit[i,1]=max_profit[i-1,0]-price[i]\n",
    "2. have 0 stock and buy 0<-max_profit[i,0]=max_profit[i-1,0]\n",
    "3. have 1 stock and sell 1<-max_profit[i,0]=max_profit[i-1,1]+price[i]\n",
    "4. have 1 stock and sell 0<-max_profit[i,1]=max_profit[i-1,1]\n",
    "\n",
    "Overall, we have the following recursions:\n",
    "\n",
    "max_profit[i,1]=max(max_profit[i-1,0]-price[i], max_profit[i-1,1])\n",
    "\n",
    "max_profit[i,0]=max(max_profit[i-1,1]+price[i], max_profit[i-1,0])\n",
    "\n",
    "If we include the cooldown, we have to denote the status by 1 and 0 on if we have sell on the day i:\n",
    "\n",
    "1. have 0 stock and buy 1<-max_profit[i,1,0]=max_profit[i-1,0,0]-price[i]\n",
    "2. have 0 stock and buy 0<-max_profit[i,0,0]=max(max_profit[i-1,0,0],max_profit[i-1,0,1])\n",
    "3. have 1 stock and sell 1<-max_profit[i,0,1]=max_profit[i-1,1,0]+price[i]\n",
    "4. have 1 stock and sell 0<-max_profit[i,1,0]=max_profit[i-1,1,0]\n",
    "\n",
    "which can be simplified as follows:\n",
    "\n",
    "max_profit[i,0]=max(max_profit[i-1,0],max_profit[i-1,1])\n",
    "\n",
    "max_profit[i,1]=max_profit[i-1,2]+price[i]\n",
    "\n",
    "max_profit[i,2]=max(max_profit[i-1,0]-price[i],max_profit[i-1,2])\n",
    "\n",
    "Base case:\n",
    "\n",
    "max_profit[1,0]=0\n",
    "\n",
    "max_profit[1,1]=0\n",
    "\n",
    "max_profit[1,2]=-price[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 85,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def maxProfit(self, prices):\n",
    "        \"\"\"\n",
    "        :type prices: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        n=len(prices)\n",
    "        if n==0: return 0\n",
    "        max_profit_0=[0]*n\n",
    "        max_profit_1=[0]*n\n",
    "        max_profit_2=[0]*n\n",
    "        max_profit_2[0]=-prices[0]\n",
    "        for i in xrange(1,n):\n",
    "            max_profit_0[i]=max(max_profit_0[i-1],max_profit_1[i-1])\n",
    "            max_profit_1[i]=max_profit_2[i-1]+prices[i]\n",
    "            max_profit_2[i]=max(max_profit_0[i-1]-prices[i],max_profit_2[i-1])\n",
    "            \n",
    "        return max(max_profit_0[n-1],max_profit_1[n-1],max_profit_2[n-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 88,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "15"
      ]
     },
     "execution_count": 88,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "prices = [2,6,8,7,8,7,9,4,1,2,4,5,8]\n",
    "o=Solution()\n",
    "o.maxProfit(prices)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 322. Coin Change"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.\n",
    "\n",
    "Example 1:\n",
    "\n",
    "coins = [1, 2, 5], amount = 11\n",
    "\n",
    "return 3 (11 = 5 + 5 + 1)\n",
    "\n",
    "Example 2:\n",
    "\n",
    "coins = [2], amount = 3\n",
    "\n",
    "return -1.\n",
    "\n",
    "Note:\n",
    "You may assume that you have an infinite number of each kind of coin.\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution: \n",
    "\n",
    "min_num[amount]= min(min_num[amount-val] for val in coins if amount>=val)+1\n",
    "\n",
    "Base case:\n",
    "min_num[0]=0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def coinChange(self, coins, amount):\n",
    "        \"\"\"\n",
    "        :type coins: List[int]\n",
    "        :type amount: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        min_num=[amount+1]*(amount+1)\n",
    "        min_num[0]=0\n",
    "        for i in xrange(1,amount+1):\n",
    "            num_set=[min_num[i-val] for val in coins if i>=val]\n",
    "            if num_set!=[]:\n",
    "                min_num[i]=min(num_set)+1\n",
    "        return min_num[amount] if min_num[amount]<=amount else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "-1"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "o=Solution()\n",
    "o.coinChange([2],5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 338. Counting Bits"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given a non negative integer number num. For every numbers i in the range 0 ≤ i ≤ num calculate the number of 1's in their binary representation and return them as an array.\n",
    "\n",
    "Example:\n",
    "For num = 5 you should return [0,1,1,2,1,2].\n",
    "\n",
    "Follow up:\n",
    "\n",
    "* It is very easy to come up with a solution with run time O(n*sizeof(integer)). But can you do it in linear time O(n) /possibly in a single pass?\n",
    "* Space complexity should be O(n).\n",
    "* Can you do it like a boss? Do it without using any builtin function like __builtin_popcount in c++ or in any other language.\n",
    "\n",
    "Hint:\n",
    "\n",
    "1. You should make use of what you have produced already.\n",
    "2. Divide the numbers in ranges like [2-3], [4-7], [8-15] and so on. And try to generate new range from previous.\n",
    "3. Or does the odd/even status of the number help you in calculating the number of 1s?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution: Brutal force: check each $0 \\leq i \\leq num$. $O(n*length_of_integer)$. Let me consider do it in a single pass. Obviously, the brutal force solution does not use the condition that the numbers are consecutive. Given num_ones[0],...,num_ones[i], what can we deduce about num_ones[i+1]:\n",
    "\n",
    "Example num=5\n",
    "\n",
    "000->001->010->011->100->101\n",
    "\n",
    "num_ones[i+1]=num_ones[i]+1 if last digit of i is 0\n",
    "num_ones[i+1]=num_ones[(i+1)/2] if last digit of i is 1\n",
    "\n",
    "base case:\n",
    "\n",
    "num_ones[0]=0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 89,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def countBits(self, num):\n",
    "        \"\"\"\n",
    "        :type num: int\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        num_ones=[0]*(num+1)\n",
    "        for i in xrange(1,num+1):\n",
    "            if (i-1)%2==0:\n",
    "                num_ones[i]=num_ones[i-1]+1\n",
    "            else:\n",
    "                num_ones[i]=num_ones[i>>1]\n",
    "        return num_ones"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 93,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 1]"
      ]
     },
     "execution_count": 93,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "o=Solution()\n",
    "o.countBits(1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 343. Integer Break"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given a positive integer n, break it into the sum of at least two positive integers and maximize the product of those integers. Return the maximum product you can get.\n",
    "\n",
    "For example, given n = 2, return 1 (2 = 1 + 1); given n = 10, return 36 (10 = 3 + 3 + 4).\n",
    "\n",
    "Note: You may assume that n is not less than 2 and not larger than 58.\n",
    "\n",
    "Hint:\n",
    "\n",
    "1. There is a simple O(n) solution to this problem.\n",
    "2. You may check the breaking results of n ranging from 7 to 10 to discover the regularities.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution: Suppose we are given the solutions for $1 \\leq i<n$: \n",
    "\n",
    "max_product[n]=max([max(i*max_product[num-i],i*(num-i)) for i in xrange(1,n)])\n",
    "\n",
    "This will take O(n^2) time. Since the hint says there is a simple O(n) solution to the problem, I will give it a try"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**O(n^2) solution**:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 100,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def integerBreak(self, n):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        max_product=[0]*(n+1)\n",
    "        max_product[0]=0\n",
    "        max_product[1]=1\n",
    "        for num in range(2,n+1):\n",
    "            max_product[num]=max([max(i*max_product[num-i],i*(num-i)) for i in xrange(1,num)])\n",
    "        return max_product[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 110,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "6"
      ]
     },
     "execution_count": 110,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "o=Solution()\n",
    "o.integerBreak(5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**O(n) solution**: For n>=7\n",
    "\n",
    "max_product[n]=3*max[n-3]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 114,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def integerBreak(self, n):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if n==2: return 1\n",
    "        if n==3: return 2\n",
    "        if n==4: return 4\n",
    "        if n==5: return 6\n",
    "        if n==6: return 9\n",
    "        max_product=[0]*(n+1)\n",
    "        max_product[4]=4\n",
    "        max_product[5]=6\n",
    "        max_product[6]=9\n",
    "        for i in xrange(7,n+1):\n",
    "            max_product[i]=3*max_product[i-3]\n",
    "        return max_product[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 115,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "36"
      ]
     },
     "execution_count": 115,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "o=Solution()\n",
    "o.integerBreak(10)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 357. Count Numbers with Unique Digits"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given a non-negative integer n, count all numbers with unique digits, x, where $0 ≤ x < 10^n$.\n",
    "\n",
    "Example:\n",
    "\n",
    "Given n = 2, return 91. (The answer should be the total numbers in the range of 0 ≤ x < 100, excluding [11,22,33,44,55,66,77,88,99])\n",
    "\n",
    "Hint:\n",
    "\n",
    "1. A direct way is to use the backtracking approach.\n",
    "2. Backtracking should contains three states which are (the current number, number of steps to get that number and a bitmask which represent which number is marked as visited so far in the current number). Start with state (0,0,0) and count all valid number till we reach number of steps equals to $10^n$.\n",
    "3. This problem can also be solved using a dynamic programming approach and some knowledge of combinatorics.\n",
    "4. Let f(k) = count of numbers with unique digits with length equals k.\n",
    "5. $f(1) = 10, ..., f(k) = 9 * 9 * 8 * ... (9 - k + 2)$ [The first factor is 9 because a number cannot start with 0]."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution: Brutal force: check the digits of every x. There is a lot of waste in this checking. If we go backwards from 10^n, then we find 10^n-1... Let me work on some simple cases n=2: 100-1=99, 100-1-11=88, 100-1-22=77, ..., 100-1-44=55; n=3: if two digits are the same, got a little stuck here. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Combinatorial solution**:\n",
    "\n",
    "f(k)=count of numbers with unique digits with length equals k.\n",
    "$$\n",
    "f(k)=9*9*8*7...*(9-(k-2))\n",
    "$$\n",
    "In particular,\n",
    "$$\n",
    "f(1)=10\n",
    "$$\n",
    "$$\n",
    "f(2)=9*9\n",
    "$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 124,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def countNumbersWithUniqueDigits(self, n):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if n==0: return 1\n",
    "        if n==1: return 10\n",
    "        if n>=11: return 0\n",
    "        f=[0]*(n+1)\n",
    "        f[1]=10\n",
    "        f[2]=81\n",
    "        result=f[1]+f[2]\n",
    "        for k in xrange(3,n+1):\n",
    "            f[k]=f[k-1]*(11-k)\n",
    "            result+=f[k]\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 128,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "32491"
      ]
     },
     "execution_count": 128,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "o=Solution()\n",
    "o.countNumbersWithUniqueDigits(5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**backtrack solution**:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 368. Largest Divisible Subset"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given a set of distinct positive integers, find the largest subset such that every pair (Si, Sj) of elements in this subset satisfies: Si % Sj = 0 or Sj % Si = 0.\n",
    "\n",
    "If there are multiple solutions, return any subset is fine.\n",
    "\n",
    "Example 1:\n",
    "\n",
    "nums: [1,2,3]\n",
    "\n",
    "Result: [1,2] (of course, [1,3] will also be ok)\n",
    "\n",
    "Example 2:\n",
    "\n",
    "nums: [1,2,4,8]\n",
    "\n",
    "Result: [1,2,4,8]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution: Discussion solution:\n",
    "\n",
    "The key concept here is:\n",
    "Given a set of integers that satisfies the property that each pair of integers inside the set are mutually divisible, for a new integer S, S can be placed into the set as long as it can divide the smallest number of the set or is divisible by the largest number of the set.\n",
    "\n",
    "For example, let's say we have a set P = { 4, 8, 16 }, P satisfies the divisible condition. Now consider a new number 2, it can divide the smallest number 4, so it can be placed into the set; similarly, 32 can be divided by 16, the biggest number in P, it can also placed into P.\n",
    "\n",
    "Next, let's define:\n",
    "\n",
    "EDIT: For clarification, the following definitions try to enlarge candidate solutions by appending a larger element at the end of each potential set, while my implementation below is prefixing a smaller element at the front of a set. Conceptually they are equivalent but by adding smaller elements at the front saves the trouble for keeping the correct increasing order for the final answer. Please refer to comments in code for more details.\n",
    "\n",
    "For an increasingly sorted array of integers a[1 .. n]\n",
    "\n",
    "T[n] = the length of the largest divisible subset whose largest number is a[n]\n",
    "\n",
    "T[n+1] = max{ 1 + T[i] if a[n+1] mod a[i] == 0 else 1 }\n",
    "\n",
    "Now, deducting T[n] becomes straight forward with a DP trick. For the final result we will need to maintain a backtrace array for the answer.\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def largestDivisibleSubset(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        nums.sort()\n",
    "        n=len(nums)\n",
    "        if n==1:\n",
    "            return [nums[0]]\n",
    "        T=[1]*n\n",
    "        parents=[None]*n\n",
    "        T_max=0\n",
    "        max_end=0\n",
    "        for j in xrange(1,n):\n",
    "            for i in xrange(j):\n",
    "                if nums[j]%nums[i]==0 and T[j]<1+T[i]:\n",
    "                    T[j]=1+T[i]\n",
    "                    parents[j]=i\n",
    "            if T[j]>T_max:\n",
    "                T_max=T[j]\n",
    "                max_end=j\n",
    "        results=[]\n",
    "        for i in xrange(T_max):\n",
    "            results.append(nums[max_end])\n",
    "            max_end=parents[max_end]\n",
    "            \n",
    "        return results"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[16, 4, 2, 1]"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "o=Solution()\n",
    "nums=[1,2,4,16,5]\n",
    "o.largestDivisibleSubset(nums)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## <font color=red>375. Guess Number Higher or Lower II(Will come back to it later by refering to decision theory or game theory)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We are playing the Guess Game. The game is as follows:\n",
    "\n",
    "I pick a number from 1 to n. You have to guess which number I picked.\n",
    "\n",
    "Every time you guess wrong, I'll tell you whether the number I picked is higher or lower.\n",
    "\n",
    "However, when you guess a particular number x, and you guess wrong, you pay $x. You win the game when you guess the number I picked.\n",
    "\n",
    "Example:\n",
    "\n",
    "n = 10, I pick 8.\n",
    "\n",
    "First round:  You guess 5, I tell you that it's higher. You pay $5.\n",
    "\n",
    "Second round: You guess 7, I tell you that it's higher. You pay $7.\n",
    "\n",
    "Third round:  You guess 9, I tell you that it's lower. You pay $9.\n",
    "\n",
    "Game over. 8 is the number I picked.\n",
    "\n",
    "You end up paying $\\$5 + \\$7 + \\$9 = \\$21$.\n",
    "\n",
    "Given a particular n ≥ 1, find out how much money you need to have to guarantee a win.\n",
    "\n",
    "Hint:\n",
    "\n",
    "* The best strategy to play the game is to minimize the maximum loss you could possibly face. Another strategy is to minimize the expected loss. Here, we are interested in the first scenario.\n",
    "* Take a small example (n = 3). What do you end up paying in the worst case?\n",
    "* Check out this article if you're still stuck.\n",
    "* The purely recursive implementation of minimax would be worthless for even a small n. You MUST use dynamic programming.\n",
    "* As a follow-up, how would you modify your code to solve the problem of minimizing the expected loss, instead of the worst-case loss?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution: "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def getMoneyAmount(self, n):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :rtype: int\n",
    "        \"\"\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 376. Wiggle Subsequence"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A sequence of numbers is called a wiggle sequence if the differences between successive numbers strictly alternate between positive and negative. The first difference (if one exists) may be either positive or negative. A sequence with fewer than two elements is trivially a wiggle sequence.\n",
    "\n",
    "For example, [1,7,4,9,2,5] is a wiggle sequence because the differences (6,-3,5,-7,3) are alternately positive and negative. In contrast, [1,4,7,2,5] and [1,7,4,5,5] are not wiggle sequences, the first because its first two differences are positive and the second because its last difference is zero.\n",
    "\n",
    "Given a sequence of integers, return the length of the longest subsequence that is a wiggle sequence. A subsequence is obtained by deleting some number of elements (eventually, also zero) from the original sequence, leaving the remaining elements in their original order.\n",
    "\n",
    "Examples:\n",
    "\n",
    "Input: [1,7,4,9,2,5]\n",
    "\n",
    "Output: 6\n",
    "\n",
    "The entire sequence is a wiggle sequence.\n",
    "\n",
    "Input: [1,17,5,10,13,15,10,5,16,8]\n",
    "\n",
    "Output: 7\n",
    "\n",
    "There are several subsequences that achieve this length. One is [1,17,10,13,10,16,8].\n",
    "\n",
    "Input: [1,2,3,4,5,6,7,8,9]\n",
    "\n",
    "Output: 2\n",
    "\n",
    "Follow up:\n",
    "\n",
    "Can you do it in O(n) time?\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution: Let me try to solve it in one pass by skipping the elements that has the same difference sign."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def wiggleMaxLength(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        n=len(nums)\n",
    "        if n<=1: return n\n",
    "        sgn=None\n",
    "        count=1\n",
    "        for i in xrange(1,n):\n",
    "            diff=nums[i]-nums[i-1]\n",
    "            if int(diff>0)!=sgn and diff!=0:\n",
    "                count+=1\n",
    "                sgn=int(diff>0)\n",
    "                \n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "7"
      ]
     },
     "execution_count": 35,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "o=Solution()\n",
    "nums=[1,17,5,10,13,15,10,5,16,8]\n",
    "o.wiggleMaxLength(nums)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**DP solution**: For every position in the array, there are only three possible statuses for it.\n",
    "\n",
    "* up position, it means nums[i] > nums[i-1]\n",
    "* down position, it means nums[i] < nums[i-1]\n",
    "* equals to position, nums[i] == nums[i-1]\n",
    "\n",
    "So we can use two arrays up[] and down[] to record the max wiggle sequence length so far at index i.\n",
    "\n",
    "If nums[i] > nums[i-1], that means it wiggles up. the element before it must be a down position. so up[i] = down[i-1] + 1; down[i] keeps the same with before.\n",
    "\n",
    "If nums[i] < nums[i-1], that means it wiggles down. the element before it must be a up position. so down[i] = up[i-1] + 1; up[i] keeps the same with before.\n",
    "\n",
    "If nums[i] == nums[i-1], that means it will not change anything becasue it didn't wiggle at all. so both down[i] and up[i] keep the same.\n",
    "\n",
    "In fact, we can reduce the space complexity to O(1), but current way is more easy to understanding."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def wiggleMaxLength(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        n=len(nums)\n",
    "        if n<=1: return n\n",
    "        up=[1]*n\n",
    "        down=[1]*n\n",
    "        for i in xrange(1,n):\n",
    "            if nums[i]>nums[i-1]:\n",
    "                up[i]=down[i-1]+1\n",
    "                down[i]=down[i-1]\n",
    "            elif nums[i]<nums[i-1]:\n",
    "                down[i]=up[i-1]+1\n",
    "                up[i]=up[i-1]\n",
    "            else:\n",
    "                down[i]=down[i-1]\n",
    "                up[i]=up[i-1]\n",
    "                \n",
    "        return max(up[n-1],down[n-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 46,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "o=Solution()\n",
    "nums=[0,0,1]\n",
    "o.wiggleMaxLength(nums)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 377. Combination Sum IV"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given an integer array with all positive numbers and no duplicates, find the number of possible combinations that add up to a positive integer target.\n",
    "\n",
    "Example:\n",
    "\n",
    "nums = [1, 2, 3]\n",
    "\n",
    "target = 4\n",
    "\n",
    "The possible combination ways are:\n",
    "\n",
    "(1, 1, 1, 1)\n",
    "\n",
    "(1, 1, 2)\n",
    "\n",
    "(1, 2, 1)\n",
    "\n",
    "(1, 3)\n",
    "\n",
    "(2, 1, 1)\n",
    "\n",
    "(2, 2)\n",
    "\n",
    "(3, 1)\n",
    "\n",
    "Note that different sequences are counted as different combinations.\n",
    "\n",
    "Therefore the output is 7.\n",
    "\n",
    "Follow up:\n",
    "* What if negative numbers are allowed in the given array?\n",
    "* How does it change the problem?\n",
    "* What limitation we need to add to the question to allow negative numbers?\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution: First we consider a recursive solution. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def combinationSum4(self, nums, target):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type target: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        results=[]\n",
    "        self.helper(nums,[],target,results)\n",
    "        return results\n",
    "        \n",
    "    def helper(self,nums,path,target,results):\n",
    "        for num in nums:\n",
    "            if target-num>0:\n",
    "                self.helper(nums,path+[num],target-num,results)\n",
    "            elif target==num:\n",
    "                path+=[num]\n",
    "                results.append(path)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[1, 1, 1, 1], [1, 1, 2], [1, 2, 1], [1, 3], [2, 1, 1], [2, 2], [3, 1]]"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "o=Solution()\n",
    "o.combinationSum4([1,2,3],4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def combinationSum4(self, nums, target):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type target: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        count=0\n",
    "        for num in nums:\n",
    "            if target-num>0:\n",
    "                count+=self.combinationSum4(nums,target-num)\n",
    "            elif target==num:\n",
    "                count+=1\n",
    "                \n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "7"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "o=Solution()\n",
    "o.combinationSum4([1,2,3],4)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The above solution is TLE as there are many duplicate subproblems in this top down approach. Then we consider bottom up approach."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def combinationSum4(self, nums, target):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type target: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        count_list=[0]*(target+1)\n",
    "        count_list[0]=1\n",
    "        for i in xrange(1,target+1):\n",
    "            count_list[i]=sum([count_list[i-num] for num in nums if i-num>=0])\n",
    "            \n",
    "        return count_list[target]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "7"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "o=Solution()\n",
    "o.combinationSum4([1,2,3],4)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 392. Is Subsequence"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given a string s and a string t, check if s is subsequence of t.\n",
    "\n",
    "You may assume that there is only lower case English letters in both s and t. t is potentially a very long (length ~= 500,000) string, and s is a short string (<=100).\n",
    "\n",
    "A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, \"ace\" is a subsequence of \"abcde\" while \"aec\" is not).\n",
    "\n",
    "Example 1:\n",
    "s = \"abc\", t = \"ahbgdc\"\n",
    "\n",
    "Return true.\n",
    "\n",
    "Example 2:\n",
    "s = \"axc\", t = \"ahbgdc\"\n",
    "\n",
    "Return false.\n",
    "\n",
    "Follow up:\n",
    "If there are lots of incoming S, say S1, S2, ... , Sk where k >= 1B, and you want to check one by one to see if T has its subsequence. In this scenario, how would you change your code?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def isSubsequence(self, s, t):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :type t: str\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        if len(s)>len(t): return False\n",
    "        p1=0\n",
    "        for p2 in t:\n",
    "            if p1<len(s) and p2==s[p1]:\n",
    "                p1+=1\n",
    "                \n",
    "        return p1==len(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "o=Solution()\n",
    "s = \"acb\"\n",
    "t = \"ahbgdc\"\n",
    "o.isSubsequence(s,t)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 413. Arithmetic Slices"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A sequence of number is called arithmetic if it consists of at least three elements and if the difference between any two consecutive elements is the same.\n",
    "\n",
    "For example, these are arithmetic sequence:\n",
    "\n",
    "1, 3, 5, 7, 9\n",
    "\n",
    "7, 7, 7, 7\n",
    "\n",
    "3, -1, -5, -9\n",
    "\n",
    "The following sequence is not arithmetic.\n",
    "\n",
    "1, 1, 2, 5, 7\n",
    "\n",
    "A zero-indexed array A consisting of N numbers is given. A slice of that array is any pair of integers (P, Q) such that 0 <= P < Q < N.\n",
    "\n",
    "A slice (P, Q) of array A is called arithmetic if the sequence:\n",
    "A[P], A[p + 1], ..., A[Q - 1], A[Q] is arithmetic. In particular, this means that P + 1 < Q.\n",
    "\n",
    "The function should return the number of arithmetic slices in the array A.\n",
    "\n",
    "\n",
    "Example:\n",
    "\n",
    "A = [1, 2, 3, 4]\n",
    "\n",
    "return: 3, for 3 arithmetic slices in A: [1, 2, 3], [2, 3, 4] and [1, 2, 3, 4] itself."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution: Brutal force solution: create a expanding window(size>=3) to check if the slice is arithmetic. O(n^2) time"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Discussion solution: We have the following recursion\n",
    "\n",
    "num_slices_end_with[i]=num_slices_end_with[i-1]+1 if A[i]-A[i-1]==A[i-1]-A[i-2] else 0\n",
    "\n",
    "Base case:\n",
    "\n",
    "num_slices_end_with[0]=num_slices_end_with[1]=0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def numberOfArithmeticSlices(self, A):\n",
    "        \"\"\"\n",
    "        :type A: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        num_slices=[0]*len(A)\n",
    "        for i in xrange(2,len(A)):\n",
    "            if A[i]-A[i-1]==A[i-1]-A[i-2]:\n",
    "                num_slices[i]=num_slices[i-1]+1\n",
    "            else:\n",
    "                num_slices[i]=0\n",
    "                \n",
    "        return sum(num_slices)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "6"
      ]
     },
     "execution_count": 47,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "o=Solution()\n",
    "A=[1, 2, 3, 4, 6, 8, 10]\n",
    "o.numberOfArithmeticSlices(A)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The above solution can be improved with an accumulative summation result to use only O(1) space."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 416. Partition Equal Subset Sum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given a non-empty array containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.\n",
    "\n",
    "Note:\n",
    "1. Each of the array element will not exceed 100.\n",
    "2. The array size will not exceed 200.\n",
    "\n",
    "Example 1:\n",
    "\n",
    "Input: [1, 5, 11, 5]\n",
    "\n",
    "Output: true\n",
    "\n",
    "Explanation: The array can be partitioned as [1, 5, 5] and [11].\n",
    "\n",
    "Example 2:\n",
    "\n",
    "Input: [1, 2, 3, 5]\n",
    "\n",
    "Output: false\n",
    "\n",
    "Explanation: The array cannot be partitioned into equal sum subsets.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution: First solution: sort the array, and then scan the array to calculate the sum of the first subset. Time O(n log n). "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def canPartition(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        nums.sort()\n",
    "        total=sum(nums)\n",
    "        left=0\n",
    "        for i in xrange(len(nums)):\n",
    "            left+=nums[i]\n",
    "            if left==total-left:\n",
    "                return True\n",
    "            \n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 52,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "o=Solution()\n",
    "nums=[1, 2, 11, 5]\n",
    "o.canPartition(nums)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The above solution is wrong for [1,2,3,4,5,6,7]. Brutal force: O(2^n) time. Improvement: store (left, right) tuple for sum[n-1] and then compute sum[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 64,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def canPartition(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        sum_collections=[(0,0)]\n",
    "        for i in xrange(len(nums)):\n",
    "            tmp=[]\n",
    "            for (left,right) in sum_collections:\n",
    "                tmp.append((left+nums[i],right))\n",
    "                tmp.append((left,right+nums[i]))\n",
    "            sum_collections=tmp\n",
    "            \n",
    "        print sum_collections\n",
    "            \n",
    "        for (left,right) in sum_collections:\n",
    "            if left==right:\n",
    "                return True\n",
    "            \n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 65,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[(28, 0), (21, 7), (22, 6), (15, 13), (23, 5), (16, 12), (17, 11), (10, 18), (24, 4), (17, 11), (18, 10), (11, 17), (19, 9), (12, 16), (13, 15), (6, 22), (25, 3), (18, 10), (19, 9), (12, 16), (20, 8), (13, 15), (14, 14), (7, 21), (21, 7), (14, 14), (15, 13), (8, 20), (16, 12), (9, 19), (10, 18), (3, 25), (26, 2), (19, 9), (20, 8), (13, 15), (21, 7), (14, 14), (15, 13), (8, 20), (22, 6), (15, 13), (16, 12), (9, 19), (17, 11), (10, 18), (11, 17), (4, 24), (23, 5), (16, 12), (17, 11), (10, 18), (18, 10), (11, 17), (12, 16), (5, 23), (19, 9), (12, 16), (13, 15), (6, 22), (14, 14), (7, 21), (8, 20), (1, 27), (27, 1), (20, 8), (21, 7), (14, 14), (22, 6), (15, 13), (16, 12), (9, 19), (23, 5), (16, 12), (17, 11), (10, 18), (18, 10), (11, 17), (12, 16), (5, 23), (24, 4), (17, 11), (18, 10), (11, 17), (19, 9), (12, 16), (13, 15), (6, 22), (20, 8), (13, 15), (14, 14), (7, 21), (15, 13), (8, 20), (9, 19), (2, 26), (25, 3), (18, 10), (19, 9), (12, 16), (20, 8), (13, 15), (14, 14), (7, 21), (21, 7), (14, 14), (15, 13), (8, 20), (16, 12), (9, 19), (10, 18), (3, 25), (22, 6), (15, 13), (16, 12), (9, 19), (17, 11), (10, 18), (11, 17), (4, 24), (18, 10), (11, 17), (12, 16), (5, 23), (13, 15), (6, 22), (7, 21), (0, 28)]\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 65,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "o=Solution()\n",
    "nums=[1, 2, 3, 4, 5, 6, 7]\n",
    "o.canPartition(nums)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The above solution is obviously MLE. We can do better with DP: our target sum is sum(nums)/2. So we create a boolean array to check if there is partial sum sums to total/2. By scanning through nums, there are two choices: \n",
    "\n",
    "1. if we include nums[i], then dp[total]=dp[total-2*nums[i]]\n",
    "2. if we do not include nums[i], then dp[total] unchanged\n",
    "\n",
    "Base case:\n",
    "\n",
    "dp[0]=True, all others will be False."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 67,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def canPartition(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        total=sum(nums)\n",
    "        dp=[False]*(total+1)\n",
    "        dp[0]=True\n",
    "        for i in xrange(len(nums)):\n",
    "            for j in xrange(total,0,-1):\n",
    "                if j>=nums[i]:\n",
    "                    dp[j]=dp[j] or dp[j-2*nums[i]]\n",
    "                    \n",
    "        return dp[total]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 69,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 69,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "o=Solution()\n",
    "nums=[1, 2, 3, 5]\n",
    "o.canPartition(nums)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**dfs solution**(TLE):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 73,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def canPartition(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        total=sum(nums)\n",
    "        nums.sort()\n",
    "        return self.dfs(nums,0,total)\n",
    "        \n",
    "    def dfs(self,nums,start,total):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type start, total: int\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        for i in xrange(start,len(nums)-1):\n",
    "            if total-2*nums[i]>0:\n",
    "                if self.dfs(nums,i+1,total-2*nums[i]):\n",
    "                    return True\n",
    "            elif total-2*nums[i]==0:\n",
    "                return True\n",
    "            \n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 75,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 75,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "o=Solution()\n",
    "nums=[1, 2, 3, 5]\n",
    "o.canPartition(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 464. Can I Win(Minmax)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In the \"100 game,\" two players take turns adding, to a running total, any integer from 1..10. The player who first causes the running total to reach or exceed 100 wins.\n",
    "\n",
    "What if we change the game so that players cannot re-use integers?\n",
    "\n",
    "For example, two players might take turns drawing from a common pool of numbers of 1..15 without replacement until they reach a total >= 100.\n",
    "\n",
    "Given an integer maxChoosableInteger and another integer desiredTotal, determine if the first player to move can force a win, assuming both players play optimally.\n",
    "\n",
    "You can always assume that maxChoosableInteger will not be larger than 20 and desiredTotal will not be larger than 300.\n",
    "\n",
    "Example\n",
    "\n",
    "Input:\n",
    "maxChoosableInteger = 10\n",
    "desiredTotal = 11\n",
    "\n",
    "Output:\n",
    "false\n",
    "\n",
    "Explanation:\n",
    "No matter which integer the first player choose, the first player will lose.\n",
    "The first player can choose an integer from 1 up to 10.\n",
    "If the first player choose 1, the second player can only choose integers from 2 up to 10.\n",
    "The second player will win by choosing 10 and get a total = 11, which is >= desiredTotal.\n",
    "Same with other integers chosen by the first player, the second player will always win."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution: The status of the current player depends on the desiredTotal and the current_set:\n",
    "\n",
    "status(current_set, desiredTotal)\n",
    "\n",
    "If there exists x in current_set>=desiredTotal, then the player can force a win, Otherwise whether he can force a win depends on the move of his opponent: \n",
    "\n",
    "If the player take a x from the current_set, his opponent cannot force a win for current_set.remove(x), desiredTotal-x, then the player can force a win with that strategy except that the maxInteger is not large enough.\n",
    "\n",
    "status(current_set, desiredTotal)=any([not status(current_set.remove(x), desiredTotal-x) for x in current_set])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Recursive solution**:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import copy\n",
    "\n",
    "class Solution(object):\n",
    "    def canIWin(self, maxChoosableInteger, desiredTotal):\n",
    "        \"\"\"\n",
    "        :type maxChoosableInteger: int\n",
    "        :type desiredTotal: int\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        if (maxChoosableInteger+1)*maxChoosableInteger<2*desiredTotal:\n",
    "            return False\n",
    "        return self.helper(range(1,maxChoosableInteger+1), desiredTotal)\n",
    "        \n",
    "    def helper(self, current_set, desiredTotal):\n",
    "        if max(current_set)>=desiredTotal:\n",
    "            return True\n",
    "        else:\n",
    "            for x in current_set:\n",
    "                new_set=copy.copy(current_set)\n",
    "                new_set.remove(x)\n",
    "                if not self.helper(new_set,desiredTotal-x):\n",
    "                    return True\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "o=Solution()\n",
    "o.canIWin(10,11)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The above solution is TLE. We need to memorize the status corresponding to the remaining set."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**DP solution**: It is important to memorize the result. We could do that by creating the hashtable with the remaining set content as the keys and the corresponding True or False as values. Bit manipulation can be very helpful."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def canIWin(self, maxChoosableInteger, desiredTotal):\n",
    "        \"\"\"\n",
    "        :type maxChoosableInteger: int\n",
    "        :type desiredTotal: int\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        if desiredTotal<=0:\n",
    "            return True\n",
    "        if (maxChoosableInteger+1)*maxChoosableInteger<2*desiredTotal:\n",
    "            return False\n",
    "        remaining=(1<<maxChoosableInteger)-1\n",
    "        self.hashtable={}\n",
    "        return self.helper(remaining,desiredTotal,maxChoosableInteger)\n",
    "    \n",
    "    def helper(self,remaining,desiredTotal,maxChoosableInteger):\n",
    "        \"\"\"\n",
    "        :type remaining: int\n",
    "        :type desiredTotal: int\n",
    "        :type maxChoosableInteger: int\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        if self.hashtable.get(remaining)!=None:\n",
    "            return self.hashtable[remaining]\n",
    "        elif desiredTotal<=0:\n",
    "            return False\n",
    "        else:\n",
    "            for i in xrange(maxChoosableInteger):\n",
    "                if ((remaining>>i)&1)==1 \\\n",
    "                and not self.helper(remaining^(1<<i),desiredTotal-(maxChoosableInteger-i),maxChoosableInteger):\n",
    "                    # memoization\n",
    "                    self.hashtable[remaining]=True\n",
    "                    return True\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 34,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "o=Solution()\n",
    "o.canIWin(10,11)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The above solution is still TLE."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 467. Unique Substrings in Wraparound String"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Consider the string s to be the infinite wraparound string of \"abcdefghijklmnopqrstuvwxyz\", so s will look like this: \"...zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd....\".\n",
    "\n",
    "Now we have another string p. Your job is to find out how many unique non-empty substrings of p are present in s. In particular, your input is the string p and you need to output the number of different non-empty substrings of p in the string s.\n",
    "\n",
    "Note: p consists of only lowercase English letters and the size of p might be over 10000.\n",
    "\n",
    "Example 1:\n",
    "\n",
    "Input: \"a\"\n",
    "\n",
    "Output: 1\n",
    "\n",
    "Explanation: Only the substring \"a\" of string \"a\" is in the string s.\n",
    "\n",
    "Example 2:\n",
    "\n",
    "Input: \"cac\"\n",
    "\n",
    "Output: 2\n",
    "\n",
    "Explanation: There are two substrings \"a\", \"c\" of string \"cac\" in the string s.\n",
    "\n",
    "Example 3:\n",
    "\n",
    "Input: \"zab\"\n",
    "\n",
    "Output: 6\n",
    "\n",
    "Explanation: There are six substrings \"z\", \"a\", \"b\", \"za\", \"ab\", \"zab\" of string \"zab\" in the string s."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution: Brutal force solution: O(n^2). Can we improve on that? Consider number of valid substring ending at index i, We have the following recursion:\n",
    "\n",
    "count[i]=count[i-1]+1 if p[i] are next to p[i-1] else 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def findSubstringInWraproundString(self, p):\n",
    "        \"\"\"\n",
    "        :type p: str\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        n=len(p)\n",
    "        if n==0: return 0\n",
    "        count=[1]*n\n",
    "        for i in xrange(1,n):\n",
    "            if ord(p[i])-ord(p[i-1])==1 or (p[i]=='a' and p[i-1]=='z'):\n",
    "                count[i]=count[i-1]+1\n",
    "            else:\n",
    "                count[i]=1\n",
    "        return sum(count)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 59,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "o=Solution()\n",
    "p=\"cac\"\n",
    "o.findSubstringInWraproundString(p)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The above solution misses the case that their could be duplicate substrings."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 70,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def findSubstringInWraproundString(self, p):\n",
    "        \"\"\"\n",
    "        :type p: str\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        alphabets=[0]*26\n",
    "        n=len(p)\n",
    "        if n==0: return 0\n",
    "        length=1\n",
    "        for i in xrange(1,n):\n",
    "            if ord(p[i])-ord(p[i-1])==1 or (p[i]=='a' and p[i-1]=='z'):\n",
    "                length+=1\n",
    "            else:\n",
    "                if length>alphabets[ord(p[i-1])-ord('a')]:\n",
    "                    alphabets[ord(p[i-1])-ord('a')]=length\n",
    "                length=1\n",
    "                \n",
    "        if length>alphabets[ord(p[n-1])-ord('a')]:\n",
    "            alphabets[ord(p[n-1])-ord('a')]=length\n",
    "                \n",
    "        count=0\n",
    "        for i in xrange(26):\n",
    "            count+=alphabets[i]*(alphabets[i]+1)/2\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 71,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4"
      ]
     },
     "execution_count": 71,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "o=Solution()\n",
    "p=\"zaba\"\n",
    "o.findSubstringInWraproundString(p)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The above solution is wrong for \"zaba\". "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 76,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def findSubstringInWraproundString(self, p):\n",
    "        \"\"\"\n",
    "        :type p: str\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        alphabets=[0]*26\n",
    "        n=len(p)\n",
    "        if n==0: return 0\n",
    "        length=1\n",
    "        alphabets[ord(p[0])-ord('a')]=length\n",
    "        for i in xrange(1,n):\n",
    "            if ord(p[i])-ord(p[i-1])==1 or (p[i]=='a' and p[i-1]=='z'):\n",
    "                length+=1\n",
    "            else:\n",
    "                length=1\n",
    "            if length>alphabets[ord(p[i])-ord('a')]:\n",
    "                alphabets[ord(p[i])-ord('a')]=length\n",
    "                      \n",
    "        return sum(alphabets)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 77,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[2, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "6"
      ]
     },
     "execution_count": 77,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "o=Solution()\n",
    "p=\"zaba\"\n",
    "o.findSubstringInWraproundString(p)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "## 474. Ones and Zeroes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In the computer world, use restricted resource you have to generate maximum benefit is what we always want to pursue.\n",
    "\n",
    "For now, suppose you are a dominator of m 0s and n 1s respectively. On the other hand, there is an array with strings consisting of only 0s and 1s.\n",
    "\n",
    "Now your task is to find the maximum number of strings that you can form with given m 0s and n 1s. Each 0 and 1 can be used at most once.\n",
    "\n",
    "Note:\n",
    "\n",
    "1. The given numbers of 0s and 1s will both not exceed 100\n",
    "2. The size of given string array won't exceed 600.\n",
    "\n",
    "Example 1:\n",
    "\n",
    "Input: Array = {\"10\", \"0001\", \"111001\", \"1\", \"0\"}, m = 5, n = 3\n",
    "\n",
    "Output: 4\n",
    "\n",
    "Explanation: This are totally 4 strings can be formed by the using of 5 0s and 3 1s, which are “10,”0001”,”1”,”0”\n",
    "\n",
    "Example 2:\n",
    "\n",
    "Input: Array = {\"10\", \"0\", \"1\"}, m = 1, n = 1\n",
    "\n",
    "Output: 2\n",
    "\n",
    "Explanation: You could form \"10\", but then you'd have nothing left. Better form \"0\" and \"1\"."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution: The discussion solution is based on the recursion\n",
    "$$\n",
    "max_covered(num_zeros,num_ones)=max(max_covered(num_zeros-str_zeros, num_ones-str_ones)+1,max_covered(num_zeros, num_ones))\n",
    "$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def findMaxForm(self, strs, m, n):\n",
    "        \"\"\"\n",
    "        :type strs: List[str]\n",
    "        :type m: int\n",
    "        :type n: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        max_covered=[[0]*(n+1) for i in xrange(m+1)]\n",
    "        length=len(strs)\n",
    "        \n",
    "        for i in xrange(length):\n",
    "            z,o=sum(1 for c in strs[i] if c == '0'), sum(1 for c in strs[i] if c == '1')\n",
    "            for j in xrange(m,-1,-1):\n",
    "                for k in xrange(n,-1,-1):\n",
    "                    if j>=z and k>=o:\n",
    "                        max_covered[j][k]=max(max_covered[j-z][k-o]+1,max_covered[j][k])\n",
    "                        \n",
    "        return max_covered[m][n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "o=Solution()\n",
    "strs=[\"10\", \"0\", \"1\"]\n",
    "o.findMaxForm(strs,1,1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 486. Predict the Winner"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given an array of scores that are non-negative integers. Player 1 picks one of the numbers from either end of the array followed by the player 2 and then player 1 and so on. Each time a player picks a number, that number will not be available for the next player. This continues until all the scores have been chosen. The player with the maximum score wins.\n",
    "\n",
    "Given an array of scores, predict whether player 1 is the winner. You can assume each player plays to maximize his score.\n",
    "\n",
    "Example 1:\n",
    "\n",
    "Input: [1, 5, 2]\n",
    "\n",
    "Output: False\n",
    "\n",
    "Explanation: Initially, player 1 can choose between 1 and 2. \n",
    "\n",
    "If he chooses 2 (or 1), then player 2 can choose from 1 (or 2) and 5. If player 2 chooses 5, then player 1 will be left with 1 (or 2). \n",
    "So, final score of player 1 is 1 + 2 = 3, and player 2 is 5. \n",
    "Hence, player 1 will never be the winner and you need to return False.\n",
    "\n",
    "Example 2:\n",
    "\n",
    "Input: [1, 5, 233, 7]\n",
    "\n",
    "Output: True\n",
    "\n",
    "Explanation: Player 1 first chooses 1. Then player 2 have to choose between 5 and 7. No matter which number player 2 choose, player 1 can choose 233.\n",
    "Finally, player 1 has more score (234) than player 2 (12), so you need to return True representing player1 can win.\n",
    "\n",
    "Note:\n",
    "1. 1 <= length of the array <= 20.\n",
    "2. Any scores in the given array are non-negative integers and will not exceed 10,000,000.\n",
    "3. If the scores of both players are equal, then player 1 is still the winner.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution: We only need to maximize the score of player1. If it exceeds half of the sum of the total score. Player 1 can win. In order to do that, we need the following recursion:\n",
    "\n",
    "$$\n",
    "score1[start,end]=max(score1[start+2,end]+array[start],score1[start+1,end-1]+array[start],score1[start+1,end-1]+array[end],score1[start,end-2]+array[end])\n",
    "$$\n",
    "\n",
    "Base case:\n",
    "\n",
    "$$\n",
    "score1[start,start]=array[start]\n",
    "$$\n",
    "$$\n",
    "score1[start,start+1]=max(array[start],array[start+1])\n",
    "$$\n",
    "\n",
    "Time complexity O(n). Space complexity O(n^2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def PredictTheWinner(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        n=len(nums)\n",
    "        score1=[[0]*n for i in xrange(n)]\n",
    "        # base case\n",
    "        for i in xrange(n):\n",
    "            score1[i][i]=nums[i]\n",
    "        for i in xrange(n-1):\n",
    "            score1[i][i+1]=max(nums[i],nums[i+1])\n",
    "        # recursion\n",
    "        for start in xrange(n-2):\n",
    "            for end in xrange(start+2,n):\n",
    "                score1[start][end]=max(score1[start+2][end]+nums[start],score1[start+1][end-1]+nums[start],\\\n",
    "                                      score1[start+1][end-1]+nums[end],score1[start][end-2]+nums[end])\n",
    "        print score1[0][n-1],sum(nums)\n",
    "        return 2*score1[0][n-1]>=sum(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "7 8\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "o=Solution()\n",
    "nums=[1, 5, 2]\n",
    "o.PredictTheWinner(nums)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The above solution is wrong as it does not maximize player2. Or Player 2 is totally idiot. Consider the discussion solution as follows:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Explanation\n",
    "\n",
    "So assuming the sum of the array it SUM, so eventually player1 and player2 will split the SUM between themselves. For player1 to win, he/she has to get more than what player2 gets. If we think from the prospective of one player, then what he/she gains each time is a plus, while, what the other player gains each time is a minus. Eventually if player1 can have a >0 total, player1 can win.\n",
    "\n",
    "Helper function simulate this process. In each round:\n",
    "\n",
    "if e==s, there is no choice but have to select nums[s]\n",
    "\n",
    "otherwise, this current player has 2 options:\n",
    "\n",
    "--> nums[s]-helper(nums,s+1,e): this player select the front item, leaving the other player a choice from s+1 to e\n",
    "\n",
    "--> nums[e]-helper(nums,s,e-1): this player select the tail item, leaving the other player a choice from s to e-1\n",
    "\n",
    "Then take the max of these two options as this player's selection, return it."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def PredictTheWinner(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        return self.helper(nums,0,len(nums)-1)>=0\n",
    "        \n",
    "    def helper(self,nums,start,end):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type start: int\n",
    "        :type end: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if start==end:\n",
    "            return nums[start]\n",
    "        else:\n",
    "            return max(nums[start]-self.helper(nums,start+1,end),nums[end]-self.helper(nums,start,end-1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "o=Solution()\n",
    "nums=[1, 5, 233, 7]\n",
    "o.PredictTheWinner(nums)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The above solution is TLE. We consider the modified recursion based on my original solution.\n",
    "\n",
    "$$\n",
    "score1[start,end]=max(min(score1[start+2,end]+array[start],score1[start+1,end-1]+array[start],min(score1[start+1,end-1]+array[end],score1[start,end-2]+array[end]))\n",
    "$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def PredictTheWinner(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        return 2*self.helper(nums,0,len(nums)-1)>=sum(nums)\n",
    "        \n",
    "    def helper(self,nums,start,end):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type start,end: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if start>end:\n",
    "            return 0\n",
    "        elif start==end:\n",
    "            return nums[start]\n",
    "        else:\n",
    "            a=min(self.helper(nums,start+2,end)+nums[start],self.helper(nums,start+1,end-1)+nums[start])\n",
    "            b=min(self.helper(nums,start+1,end-1)+nums[end],self.helper(nums,start,end-2)+nums[end])\n",
    "            print a,b\n",
    "            return max(a,b)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 99\n",
      "1 1\n",
      "1 1\n",
      "567 1\n",
      "568 100\n",
      "1 1\n",
      "567 1\n",
      "567 1\n",
      "1 567\n",
      "2 568\n",
      "1 1\n",
      "567 1\n",
      "567 1\n",
      "1 567\n",
      "2 568\n",
      "567 1\n",
      "1 567\n",
      "1 567\n",
      "1 1\n",
      "568 2\n",
      "569 667\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "o=Solution()\n",
    "nums=[1,1,567,1,1,99]\n",
    "o.PredictTheWinner(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def PredictTheWinner(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        n=len(nums)\n",
    "        score1=[[0]*n for i in xrange(n)]\n",
    "        # base case\n",
    "        for i in xrange(n):\n",
    "            score1[i][i]=nums[i]\n",
    "        for i in xrange(n-1):\n",
    "            score1[i][i+1]=max(nums[i],nums[i+1])\n",
    "        # recursion\n",
    "        for width in xrange(2,n):\n",
    "            for start in xrange(0,n-width):\n",
    "                end=start+width\n",
    "                a=min(score1[start+2][end]+nums[start],score1[start+1][end-1]+nums[start])\n",
    "                b=min(score1[start+1][end-1]+nums[end],score1[start][end-2]+nums[end])\n",
    "                score1[start][end]=max(a,b)\n",
    "\n",
    "        return 2*score1[0][n-1]>=sum(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 40,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "o=Solution()\n",
    "nums=[1,1,567,1,1,99]\n",
    "o.PredictTheWinner(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.12"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}