11_Dynamic_Programming.ipynb

{"cells":[{"attachments":{},"cell_type":"markdown","metadata":{"id":"yDj9iVXUDThT"},"source":["# **Dynamic Programming Intro**\n","\n","Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping subproblems in a recursive manner and use solutions to the subproblems to construct solution to the original problem.\n","\n","A problem is a dynamic programming problem if it satisfies two conditions:\n","\n","1. The problem can be divided into subproblems, and its optimal solution can be constructed from optimal solutions of the subproblems.\n","2. The subproblems from 1) overlap.\n"]},{"attachments":{},"cell_type":"markdown","metadata":{"id":"cG6xP9zwKX_r"},"source":["# **Top-down vs Bottom-up**\n","\n","There are two different approaches to DP: one is top-down, the other one is bottom-up.\n","\n","* **Top-down:** this is basically DFS + memoization. We split large problems and recursively solve smaller subproblems.\n","\n","* **Bottom-up:** we try to solve subproblems first and then use their solutions to find solutions to bigger subproblems. This is normally done by filling up a table.\n","\n"]},{"attachments":{},"cell_type":"markdown","metadata":{"id":"oIaJL0OuKoI2"},"source":["# **Example: Function returning the `n`th Fibonacci number**\n","\n","The Fibonacci sequence begins with the numbers `0` and `1`, and each subsequent number is the sum of the previous two numbers of the sequence:  `0,1,1,2,3,5,8,13,21,34,55...`"]},{"cell_type":"code","execution_count":1,"metadata":{"executionInfo":{"elapsed":148,"status":"ok","timestamp":1673721791927,"user":{"displayName":"Suzana Milea","userId":"14631860544657795687"},"user_tz":480},"id":"4gRvmHThLrWD"},"outputs":[],"source":["# Top-down with Memoization\n","# Time: O(n)\n","\n","def fib(n, memo={}):\n","\n","  if n == 0 or n == 1:\n","    return n\n","\n","  if not memo.get(n):\n","    memo[n] = fib(n-1, memo) + fib(n-2, memo)\n","\n","  return memo[n]  "]},{"cell_type":"markdown","metadata":{"id":"xK9RzccG51C_"},"source":["We want to fill a one-dimensional table `dp` where each entry at index `i` represents value of the Fibonacci number at index `i`. The last element of the array is the result we want to return.\n","\n","The order of filling matters because we cannot calculate `dp[i]` before we filled `dp[i - 1]` and `dp[i - 2]`."]},{"cell_type":"code","execution_count":2,"metadata":{"executionInfo":{"elapsed":149,"status":"ok","timestamp":1673721793944,"user":{"displayName":"Suzana Milea","userId":"14631860544657795687"},"user_tz":480},"id":"nIZE5Y7M6MLA"},"outputs":[],"source":["# Bottom up with Tabulation\n","def fib(n):\n","  dp = [0,1]\n","  for i in range(2,n+1):\n","    dp.append(dp[i-1] + dp[i-2])\n","  return dp[-1]    "]},{"cell_type":"code","execution_count":3,"metadata":{"colab":{"base_uri":"https://localhost:8080/"},"executionInfo":{"elapsed":148,"status":"ok","timestamp":1673721795396,"user":{"displayName":"Suzana Milea","userId":"14631860544657795687"},"user_tz":480},"id":"YVaZ5crXMUVb","outputId":"0d79896e-3519-4867-815d-c4afdc86e1c3"},"outputs":[{"data":{"text/plain":["21"]},"execution_count":3,"metadata":{},"output_type":"execute_result"}],"source":["fib(8)"]},{"cell_type":"markdown","metadata":{"id":"Mmquslfb9zKL"},"source":["The concept of DP is quite simple - find the overlapping subproblems, solve them and use the subproblem solutions to find the solution to the original problem. The hard part is to know how to find the recurrence relation.\n","For the Fibonacci number problem, the recurrence relation `dp[i] = dp[i - 1] + dp[i - 2]` is already given . "]},{"attachments":{},"cell_type":"markdown","metadata":{"id":"haZ4BYOhEP9w"},"source":["# **Leetcode 70. Climbing Stairs** `Easy`\n","\n","You are climbing a staircase. It takes `n` steps to reach 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?\n","\n","``` \n","Example 1:\n","Input: n = 2\n","Output: 2\n","Explanation: There are two ways to climb to the top.\n","1. 1 step + 1 step\n","2. 2 steps\n","\n","Example 2:\n","Input: n = 3\n","Output: 3\n","Explanation: There are three ways to climb to the top.\n","1. 1 step + 1 step + 1 step\n","2. 1 step + 2 steps\n","3. 2 steps + 1 step\n"," \n","\n","Constraints:\n","1 <= n <= 45\n","```"]},{"cell_type":"code","execution_count":4,"metadata":{"executionInfo":{"elapsed":151,"status":"ok","timestamp":1673721799783,"user":{"displayName":"Suzana Milea","userId":"14631860544657795687"},"user_tz":480},"id":"XyAEPsme-QvQ"},"outputs":[],"source":["# Bottom-up DP\n","def climbStairs(n: int) -> int:\n","  dp = [1,1]\n","\n","  for i in range(2,n+1):\n","    dp.append(dp[i-1]+dp[i-2])\n","  return dp[-1]  \n"]},{"cell_type":"code","execution_count":5,"metadata":{"executionInfo":{"elapsed":2,"status":"ok","timestamp":1673721801203,"user":{"displayName":"Suzana Milea","userId":"14631860544657795687"},"user_tz":480},"id":"d01VnLSNFfxL"},"outputs":[],"source":["# Top-down DP\n","\n","def climbStairs(n: int, memo = {}) -> int:\n","  \n","  if n == 0 or n == 1:\n","    return 1\n","\n","  elif n in memo:\n","    return memo[n]\n","    \n","  else:\n","    memo[n] = climbStairs(n - 2, memo) + climbStairs(n - 1, memo)\n","\n","  return memo[n]\n","        "]},{"cell_type":"code","execution_count":6,"metadata":{"colab":{"base_uri":"https://localhost:8080/"},"executionInfo":{"elapsed":148,"status":"ok","timestamp":1673721803563,"user":{"displayName":"Suzana Milea","userId":"14631860544657795687"},"user_tz":480},"id":"WhDXHHfkFCSB","outputId":"1d1d94ba-a8be-401f-dc74-0aca3e73d61b"},"outputs":[{"data":{"text/plain":["3"]},"execution_count":6,"metadata":{},"output_type":"execute_result"}],"source":["climbStairs(3)"]},{"attachments":{},"cell_type":"markdown","metadata":{"id":"ZI_zKER31UOV"},"source":["# **Leetcode 746. Min Cost Climbing Stairs** `Easy`\n","\n","You are given an integer array cost where `cost[i]` is the cost of `i`th step on a staircase. Once you pay the cost, you can either climb one or two steps.\n","\n","You can either start from the step with index `0`, or the step with index `1`.\n","\n","Return the minimum cost to reach the top of the floor.\n","\n","``` \n","Example 1:\n","Input: cost = [10,15,20]\n","Output: 15\n","Explanation: You will start at index 1.\n","- Pay 15 and climb two steps to reach the top.\n","The total cost is 15.\n","\n","Example 2:\n","Input: cost = [1,100,1,1,1,100,1,1,100,1]\n","Output: 6\n","Explanation: You will start at index 0.\n","- Pay 1 and climb two steps to reach index 2.\n","- Pay 1 and climb two steps to reach index 4.\n","- Pay 1 and climb two steps to reach index 6.\n","- Pay 1 and climb one step to reach index 7.\n","- Pay 1 and climb two steps to reach index 9.\n","- Pay 1 and climb one step to reach the top.\n","The total cost is 6.\n"," \n","Constraints:\n","2 <= cost.length <= 1000\n","0 <= cost[i] <= 999\n","```"]},{"cell_type":"code","execution_count":7,"metadata":{"executionInfo":{"elapsed":148,"status":"ok","timestamp":1673721808654,"user":{"displayName":"Suzana Milea","userId":"14631860544657795687"},"user_tz":480},"id":"2g8hAvvg1pCM"},"outputs":[],"source":["# Time: O(n), Space: O(n)\n","\n","def minCostClimbingStairs(cost) -> int:\n","        \n","        f = [0, cost[-1], cost[-2]]      \n","        n = len(cost)\n","        \n","        for i in range(n-3, -1, -1):\n","            f.append(cost[i] + min(f[n-i-1], f[n-i-2]))\n","        \n","        return min(f[-1], f[-2])\n","        "]},{"cell_type":"code","execution_count":8,"metadata":{"executionInfo":{"elapsed":189,"status":"ok","timestamp":1673721656090,"user":{"displayName":"Suzana Milea","userId":"14631860544657795687"},"user_tz":480},"id":"cp1LJY8-9pAX"},"outputs":[],"source":["# Time: O(n), Space: O(1)\n","\n","def minCostClimbingStairs(cost) -> int:\n","\n","  cost.append(0)\n","\n","  for i in range(len(cost)-3, -1, -1):\n","    cost[i] += min(cost[i+1], cost[i+2])\n","\n","  return min(cost[0], cost[1])  \n","\n"]},{"cell_type":"code","execution_count":9,"metadata":{"colab":{"base_uri":"https://localhost:8080/"},"executionInfo":{"elapsed":173,"status":"ok","timestamp":1673721659311,"user":{"displayName":"Suzana Milea","userId":"14631860544657795687"},"user_tz":480},"id":"giQyNDgv145U","outputId":"b3deacc5-9b3d-4300-c20c-4fc27da52d43"},"outputs":[{"data":{"text/plain":["6"]},"execution_count":9,"metadata":{},"output_type":"execute_result"}],"source":["cost = [1,100,1,1,1,100,1,1,100,1]\n","minCostClimbingStairs(cost)"]},{"attachments":{},"cell_type":"markdown","metadata":{"id":"cxFebbM0A98S"},"source":["# **Leetcode 198. House Robber** `Medium`\n","\n","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 systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night.\n","\n","Given an integer array `nums` representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.\n","\n","``` \n","Example 1:\n","Input: nums = [1,2,3,1]\n","Output: 4\n","Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).\n","Total amount you can rob = 1 + 3 = 4.\n","\n","Example 2:\n","Input: nums = [2,7,9,3,1]\n","Output: 12\n","Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1).\n","Total amount you can rob = 2 + 9 + 1 = 12.\n"," \n","\n","Constraints:\n","1 <= nums.length <= 100\n","0 <= nums[i] <= 400\n","```"]},{"cell_type":"code","execution_count":10,"metadata":{"executionInfo":{"elapsed":165,"status":"ok","timestamp":1673721672397,"user":{"displayName":"Suzana Milea","userId":"14631860544657795687"},"user_tz":480},"id":"3FMqLztvBYx8"},"outputs":[],"source":["def rob(nums) -> int:\n","    nums.append(0)  \n","    \n","    for i in range(len(nums)-4, -1, -1):\n","        nums[i] += max(nums[i+2], nums[i+3])\n","\n","    return max(nums[0], nums[1])  \n","    "]},{"cell_type":"code","execution_count":11,"metadata":{"executionInfo":{"elapsed":192,"status":"ok","timestamp":1673721681914,"user":{"displayName":"Suzana Milea","userId":"14631860544657795687"},"user_tz":480},"id":"ilx7qA5fKXsF"},"outputs":[],"source":["def rob(nums) -> int:\n","    rob1, rob2 = 0,0\n","    \n","    # [rob1,rob2,num,*,...]\n","    for num in nums:\n","        newRob = max(rob1 + num, rob2)\n","        rob1 = rob2\n","        rob2 = newRob\n","        \n","    return rob2    "]},{"cell_type":"code","execution_count":12,"metadata":{"colab":{"base_uri":"https://localhost:8080/"},"executionInfo":{"elapsed":263,"status":"ok","timestamp":1652757237321,"user":{"displayName":"Suzana Serboi","userId":"10724376308974132887"},"user_tz":420},"id":"VcfDTpNSBwf7","outputId":"839a33cf-27b2-4d29-d16f-4b2e86bb5303"},"outputs":[{"data":{"text/plain":["11"]},"execution_count":12,"metadata":{},"output_type":"execute_result"}],"source":["nums = [2,1,1,9,1]\n","rob(nums)"]},{"attachments":{},"cell_type":"markdown","metadata":{"id":"xxG9tOOgC0jA"},"source":["# **Leetcode 213. House Robber II** `Medium`\n","\n","You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. All houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, adjacent houses have a security system connected, and it will automatically contact the police if two adjacent houses were broken into on the same night.\n","\n","Given an integer array `nums` representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.\n","\n"," \n","```\n","Example 1:\n","Input: nums = [2,3,2]\n","Output: 3\n","Explanation: You cannot rob house 1 (money = 2) and then rob house 3 (money = 2), because they are adjacent houses.\n","\n","Example 2:\n","Input: nums = [1,2,3,1]\n","Output: 4\n","Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).\n","Total amount you can rob = 1 + 3 = 4.\n","\n","Example 3:\n","Input: nums = [1,2,3]\n","Output: 3\n"," \n","Constraints:\n","1 <= nums.length <= 100\n","0 <= nums[i] <= 1000\n","```"]},{"cell_type":"code","execution_count":13,"metadata":{"executionInfo":{"elapsed":140,"status":"ok","timestamp":1673721695841,"user":{"displayName":"Suzana Milea","userId":"14631860544657795687"},"user_tz":480},"id":"vLK0ctyUDF7B"},"outputs":[],"source":["def rob2(nums) -> int:\n","      if len(nums) == 1:\n","          return nums[0]\n","      \n","      def rob1(arr):\n","          arr.append(0)  \n","          for i in range(len(arr)-4, -1, -1):\n","              arr[i] += max(arr[i+2], arr[i+3])\n","          return max(arr[0], arr[1])  \n","      \n","      x = rob1(nums[1:])\n","      y = rob1(nums[:-1])\n","      return max(x,y)"]},{"cell_type":"code","execution_count":14,"metadata":{"executionInfo":{"elapsed":154,"status":"ok","timestamp":1673721706995,"user":{"displayName":"Suzana Milea","userId":"14631860544657795687"},"user_tz":480},"id":"zQFByrJODgX8"},"outputs":[],"source":["def rob(nums) -> int:\n","        if len(nums) == 1:\n","            return nums[0]\n","        \n","        def rob1(arr):\n","            rob1, rob2 = 0, 0\n","            for house in arr:\n","                newRob = max(rob1 + house, rob2)\n","                rob1 = rob2\n","                rob2 = newRob\n","            return rob2\n","        \n","        return max(rob1(nums[1:]), rob1(nums[:-1]))\n","        "]},{"cell_type":"code","execution_count":15,"metadata":{"colab":{"base_uri":"https://localhost:8080/"},"executionInfo":{"elapsed":195,"status":"ok","timestamp":1652758040587,"user":{"displayName":"Suzana Serboi","userId":"10724376308974132887"},"user_tz":420},"id":"8_UdMuh9DSUX","outputId":"49e29532-3e6a-4b02-acac-528d64c18f01"},"outputs":[{"data":{"text/plain":["3"]},"execution_count":15,"metadata":{},"output_type":"execute_result"}],"source":["nums = [2,3,2]\n","rob2(nums)"]},{"attachments":{},"cell_type":"markdown","metadata":{"id":"8Jzys0lxSBBC"},"source":["# **Leetcode 139. Word Break** `Medium`\n","\n","Given a string `s` and a dictionary of strings `wordDict`, return `true` if `s` can be segmented into a space-separated sequence of one or more dictionary words.\n","\n","Note that the same word in the dictionary may be reused multiple times in the segmentation.\n","\n","```\n","Example 1:\n","Input: s = \"leetcode\", wordDict = [\"leet\",\"code\"]\n","Output: true\n","Explanation: Return true because \"leetcode\" can be segmented as \"leet code\".\n","\n","Example 2:\n","Input: s = \"applepenapple\", wordDict = [\"apple\",\"pen\"]\n","Output: true\n","Explanation: Return true because \"applepenapple\" can be segmented as \"apple pen apple\".\n","Note that you are allowed to reuse a dictionary word.\n","\n","Example 3:\n","Input: s = \"catsandog\", wordDict = [\"cats\",\"dog\",\"sand\",\"and\",\"cat\"]\n","Output: false\n","\n"]},{"cell_type":"code","execution_count":16,"metadata":{"executionInfo":{"elapsed":167,"status":"ok","timestamp":1673721721348,"user":{"displayName":"Suzana Milea","userId":"14631860544657795687"},"user_tz":480},"id":"1O9XPKa5SUa_"},"outputs":[],"source":["def wordBreak(s: str, wordDict) -> bool:\n","        \n","        dp = [False] * (len(s)+1)\n","        dp[len(s)] = True\n","        \n","        for i in range(len(s)-1,-1,-1):\n","            for word in set(wordDict):\n","                if i + len(word) <= len(s) and s[i:i+len(word)] == word:\n","                    dp[i] = dp[i+len(word)]\n","                if dp[i]:\n","                    break\n","        return dp[0]            \n","        "]},{"cell_type":"code","execution_count":17,"metadata":{"executionInfo":{"elapsed":146,"status":"ok","timestamp":1673721731680,"user":{"displayName":"Suzana Milea","userId":"14631860544657795687"},"user_tz":480},"id":"06w9uAD8UMuZ"},"outputs":[],"source":["def wordBreak(s: str, wordDict) -> bool:\n","        \n","        dp = [False] * (len(s) + 1)\n","        dp[0] = True\n","        # bool_list[i] is True means s[:i] can be segmented into words in the wordDicts \n","     \n","        for i in range(len(s)):\n","            for j in range(i, len(s)):\n","                if dp[i] and s[i:j+1] in set(wordDict):\n","                    dp[j+1] = True\n","        return dp[-1]\n","    "]},{"cell_type":"code","execution_count":18,"metadata":{"colab":{"base_uri":"https://localhost:8080/"},"executionInfo":{"elapsed":218,"status":"ok","timestamp":1652762417616,"user":{"displayName":"Suzana Serboi","userId":"10724376308974132887"},"user_tz":420},"id":"3NmqyJ3rShK-","outputId":"bb09d01f-c952-4732-b47e-ee667ca3df78"},"outputs":[{"data":{"text/plain":["False"]},"execution_count":18,"metadata":{},"output_type":"execute_result"}],"source":["s = \"catsandog\"\n","wordDict = [\"cats\",\"dog\",\"sand\",\"and\",\"cat\"]\n","wordBreak(s, wordDict)"]},{"attachments":{},"cell_type":"markdown","metadata":{"id":"BBFR-GbL7MwY"},"source":["# **Leetcode 5. Longest Palindromic Substring** `Medium`\n","\n","Given a string `s`, return the longest palindromic substring in `s`.\n","\n","```\n","Example 1:\n","Input: s = \"babad\"\n","Output: \"bab\"\n","Explanation: \"aba\" is also a valid answer.\n","\n","Example 2:\n","Input: s = \"cbbd\"\n","Output: \"bb\"\n"," \n","Constraints:\n","1 <= s.length <= 1000\n","s consist of only digits and English letters.\n","```\n","\n"]},{"cell_type":"code","execution_count":19,"metadata":{"id":"jkxqCtis7bq3"},"outputs":[],"source":["def longestPalindrome(s: str) -> str:\n","        \n","        def helper(l, r):\n","            while l >= 0 and r < len(s) and s[l] == s[r]:\n","                l -= 1\n","                r += 1\n","            return s[l+1: r]    \n","        \n","        res = \"\"\n","        for i in range(len(s)): \n","            # even length\n","            string = helper(i,i)\n","            if len(string) > len(res):\n","                res = string\n","            # odd length    \n","            string = helper(i,i+1)\n","            if len(string) > len(res):\n","                res = string    \n","                \n","        return res          "]},{"cell_type":"code","execution_count":20,"metadata":{"colab":{"base_uri":"https://localhost:8080/","height":36},"executionInfo":{"elapsed":166,"status":"ok","timestamp":1652856674812,"user":{"displayName":"Suzana Serboi","userId":"10724376308974132887"},"user_tz":420},"id":"ZKreP2_O7uDM","outputId":"d36a7c34-5e43-4661-9fcd-d88c7f282837"},"outputs":[{"data":{"text/plain":["'bab'"]},"execution_count":20,"metadata":{},"output_type":"execute_result"}],"source":["s = \"babad\"\n","longestPalindrome(s)"]},{"attachments":{},"cell_type":"markdown","metadata":{"id":"LuFGw5sknOox"},"source":["# **Leetcode 647. Palindromic Substrings** `Medium`\n","\n","Given a string `s`, return the number of palindromic substrings in it.\n","\n","A string is a palindrome when it reads the same backward as forward.\n","\n","A substring is a contiguous sequence of characters within the string.\n","\n"," \n","```\n","Example 1:\n","Input: s = \"abc\"\n","Output: 3\n","Explanation: Three palindromic strings: \"a\", \"b\", \"c\".\n","\n","Example 2:\n","Input: s = \"aaa\"\n","Output: 6\n","Explanation: Six palindromic strings: \"a\", \"a\", \"a\", \"aa\", \"aa\", \"aaa\".\n"," \n","Constraints:\n","1 <= s.length <= 1000\n","s consists of lowercase English letters.\n","```\n","\n"]},{"cell_type":"code","execution_count":21,"metadata":{"id":"KNYWPM2WndK2"},"outputs":[],"source":["# Time: O(n^2)\n","def countSubstrings(s: str) -> int:\n","        res = 0\n","        \n","        def helper(l,r):\n","            count = 0\n","            while l >= 0 and r < len(s) and s[l] == s[r]:\n","                l -= 1\n","                r += 1\n","                count += 1\n","            return count\n","        \n","        for i in range(len(s)):\n","            # odd length palindromes\n","            res += helper(i,i)\n","            \n","            # even length palindromes\n","            res += helper(i,i+1)\n","                \n","        return res"]},{"cell_type":"code","execution_count":22,"metadata":{"colab":{"base_uri":"https://localhost:8080/"},"executionInfo":{"elapsed":225,"status":"ok","timestamp":1653031756018,"user":{"displayName":"Suzana Serboi","userId":"10724376308974132887"},"user_tz":420},"id":"2RvQGF76uvMB","outputId":"a73f514c-36e4-4fd3-df95-0279aeda6ba3"},"outputs":[{"data":{"text/plain":["6"]},"execution_count":22,"metadata":{},"output_type":"execute_result"}],"source":["s = \"aaa\"\n","countSubstrings(s)"]},{"attachments":{},"cell_type":"markdown","metadata":{"id":"hskNZUZNXrgG"},"source":["# **Leetcode 322. Coin Change** `Medium`\n","\n","You are given an integer array `coins` representing coins of different denominations and an integer amount representing a total amount of money.\n","\n","Return 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","You may assume that you have an infinite number of each kind of coin.\n","\n"," \n","```\n","Example 1:\n","Input: coins = [1,2,5], amount = 11\n","Output: 3\n","Explanation: 11 = 5 + 5 + 1\n","\n","Example 2:\n","Input: coins = [2], amount = 3\n","Output: -1\n","\n","Example 3:\n","Input: coins = [1], amount = 0\n","Output: 0\n"," \n","Constraints:\n","\n","1 <= coins.length <= 12\n","1 <= coins[i] <= 231 - 1\n","0 <= amount <= 104\n","```"]},{"cell_type":"code","execution_count":23,"metadata":{"executionInfo":{"elapsed":161,"status":"ok","timestamp":1673721761871,"user":{"displayName":"Suzana Milea","userId":"14631860544657795687"},"user_tz":480},"id":"qh1IyY87YQB-"},"outputs":[],"source":["def coinChange(coins, amount: int) -> int:\n","  dp = [amount + 1] * (amount + 1)\n","  dp[0] = 0\n","\n","  for c in coins:\n","    for i in range(1,amount + 1):\n","      if i - c >= 0:\n","        dp[i] = min(dp[i], dp[i-c] + 1)\n","  if dp[amount] != amount + 1:\n","    return dp[amount]\n","  else:\n","    return -1          "]},{"cell_type":"code","execution_count":24,"metadata":{"colab":{"base_uri":"https://localhost:8080/"},"executionInfo":{"elapsed":147,"status":"ok","timestamp":1673721771083,"user":{"displayName":"Suzana Milea","userId":"14631860544657795687"},"user_tz":480},"id":"UbgCeo6CZQer","outputId":"51996949-efea-4901-e9cc-2081cf87a4fd"},"outputs":[{"data":{"text/plain":["3"]},"execution_count":24,"metadata":{},"output_type":"execute_result"}],"source":["coins = [1,2,5]\n","amount = 11\n","coinChange(coins, amount)"]},{"attachments":{},"cell_type":"markdown","metadata":{"id":"sd4Vs946ratv"},"source":["# **Leetcode 152. Maximum Product Subarray** `Medium`\n","\n","Given an integer array `nums`, find a contiguous non-empty subarray within the array that has the largest product, and return the product.\n","\n","The test cases are generated so that the answer will fit in a 32-bit integer.\n","\n","A subarray is a contiguous subsequence of the array.\n","\n"," \n","```\n","Example 1:\n","Input: nums = [2,3,-2,4]\n","Output: 6\n","Explanation: [2,3] has the largest product 6.\n","\n","Example 2:\n","Input: nums = [-2,0,-1]\n","Output: 0\n","Explanation: The result cannot be 2, because [-2,-1] is not a subarray.\n"," \n","Constraints:\n","1 <= nums.length <= 2 * 104\n","-10 <= nums[i] <= 10\n","The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.\n","```"]},{"cell_type":"code","execution_count":25,"metadata":{"executionInfo":{"elapsed":135,"status":"ok","timestamp":1673721782332,"user":{"displayName":"Suzana Milea","userId":"14631860544657795687"},"user_tz":480},"id":"g682sjACru5H"},"outputs":[],"source":["def maxProduct(nums) -> int:\n","  res = max(nums)\n","  curMax, curMin = 1,1\n","\n","  for n in nums:\n","    if n == 0:\n","      curMax, curMin = 1,1\n","      continue\n","    temp = curMax * n\n","    curMax = max(temp, curMin * n, n)\n","    curMin = min(temp, curMin * n, n)\n","    res = max(res, curMax)\n","  return res      "]},{"cell_type":"code","execution_count":26,"metadata":{"colab":{"base_uri":"https://localhost:8080/"},"executionInfo":{"elapsed":155,"status":"ok","timestamp":1673721785375,"user":{"displayName":"Suzana Milea","userId":"14631860544657795687"},"user_tz":480},"id":"f0-SQ3n5tEFR","outputId":"24906328-07c0-48d6-a252-e2fc666fb916"},"outputs":[{"data":{"text/plain":["6"]},"execution_count":26,"metadata":{},"output_type":"execute_result"}],"source":["nums = [2,3,-2,4]\n","maxProduct(nums)"]}],"metadata":{"colab":{"provenance":[]},"kernelspec":{"display_name":"Python 3","language":"python","name":"python3"},"language_info":{"codemirror_mode":{"name":"ipython","version":3},"file_extension":".py","mimetype":"text/x-python","name":"python","nbconvert_exporter":"python","pygments_lexer":"ipython3","version":"3.11.3"},"vscode":{"interpreter":{"hash":"eebfdcaa29e42ce6b9e87bbf090238f6b02a61a67ece652be53a811344c78d0d"}}},"nbformat":4,"nbformat_minor":0}