{"id":9059,"date":"2021-12-05T20:48:59","date_gmt":"2021-12-06T04:48:59","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=9059"},"modified":"2021-12-06T18:38:18","modified_gmt":"2021-12-07T02:38:18","slug":"leetcode-ultimate-dp-study-plan-day-7","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/dynamic-programming\/leetcode-ultimate-dp-study-plan-day-7\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode Ultimate DP Study Plan Day 7"},"content":{"rendered":"\n<figure class=\"wp-block-embed is-type-video is-provider-youtube wp-block-embed-youtube wp-embed-aspect-4-3 wp-has-aspect-ratio\"><div class=\"wp-block-embed__wrapper\">\n<iframe loading=\"lazy\" title=\"LeetCode DP\u7ec8\u6781\u5b66\u4e60\u8ba1\u5212\uff01Day7 | Best Time to Buy and Sell Stock\u3010\u8ddf\u6211\u4e00\u8d77\u5199\u4ee3\u7801\u3011\" width=\"500\" height=\"281\" src=\"https:\/\/www.youtube.com\/embed\/iTyEa35Ve-U?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe>\n<\/div><\/figure>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>1014.&nbsp;Best Sightseeing Pair<\/strong><\/h2>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">Python3<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"python\">\n# Author: Huahua\n# Time complexity: O(n)\n# Space complexity: O(n)\nclass Solution:\n  def maxScoreSightseeingPair(self, values: List[int]) -> int:    \n    # score = (values[i] + i) + (values[j] - j)\n    @cache\n    def dp(j: int) -> Tuple[int, int]:\n      \"\"\"Returns:\n        1) Max score of values[0..j]\n        2) Largest values[i] + i (i <= j).\"\"\"\n      if j < 0: return 0, 0\n      s, v = dp(j - 1)\n      return max(s, v + values[j] - j), max(v, values[j] + j)\n    \n    return dp(len(values) - 1)[0]\n<\/pre>\n<\/div><\/div>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>121.&nbsp;Best Time to Buy and Sell Stock<\/strong><\/h2>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">Python3<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"python\">\n# Author: Huahua\n# Time complexity: O(n)\n# Space complexity: O(n)\nclass Solution:\n  def maxProfit(self, prices: List[int]) -> int:\n    @cache\n    def dp(i: int) -> Tuple[int, int]:\n      \"\"\"Returns:\n        1) max profit of prices[0:i].\n        2) min price of prices[0:i].\"\"\"\n      if i < 0: return 0, 10**9\n      max_profit, min_price = dp(i - 1)\n      return max(max_profit, prices[i] - min_price), min(min_price, prices[i])\n\n    return dp(len(prices) - 1)[0]\n<\/pre>\n<\/div><\/div>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>122.&nbsp;Best Time to Buy and Sell Stock II<\/strong><\/h2>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">Python3<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"python\">\n# Author: Huahua\n# Time complexity: O(n)\n# Space complexity: O(n)\nclass Solution:\n  def maxProfit(self, prices: List[int]) -> int:\n    \n    @cache\n    def dp(i: int) -> Tuple[int, int]:\n      \"\"\"Returns:\n      1) Max profit after i-th day. Holding no stocks. Can buy.\n      2) Max balance after i-th day. Holding a stock. Can sell.\n      \"\"\"\n      if i < 0: return 0, -10**9\n      profit, balance = dp(i - 1)\n      \n      return (max(profit, balance + prices[i]), # do nothing, sell\n              max(balance, profit - prices[i]))  # do nothing, buy\n    \n    return dp(len(prices) - 1)[0]\n<\/pre>\n<\/div><\/div>\n\n\n\n<p><\/p>\n","protected":false},"excerpt":{"rendered":"<p>1014.&nbsp;Best Sightseeing Pair # Author: Huahua # Time complexity: O(n) # Space complexity: O(n) class Solution: def maxScoreSightseeingPair(self, values: List[int]) -> int: # score =&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[46],"tags":[18,743],"class_list":["post-9059","post","type-post","status-publish","format-standard","hentry","category-dynamic-programming","tag-dp","tag-ultimate-dp-study-plan","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9059","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=9059"}],"version-history":[{"count":4,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9059\/revisions"}],"predecessor-version":[{"id":9064,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9059\/revisions\/9064"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=9059"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=9059"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=9059"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}