{"id":8943,"date":"2021-11-30T23:10:29","date_gmt":"2021-12-01T07:10:29","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=8943"},"modified":"2021-11-30T23:19:51","modified_gmt":"2021-12-01T07:19:51","slug":"leetcode-ultimate-dp-study-plan-day-1-3","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/dynamic-programming\/leetcode-ultimate-dp-study-plan-day-1-3\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode Ultimate DP Study Plan Day 1 &#8211; 3"},"content":{"rendered":"\n<figure class=\"wp-block-embed is-type-video is-provider-youtube wp-block-embed-youtube wp-embed-aspect-16-9 wp-has-aspect-ratio\"><div class=\"wp-block-embed__wrapper\">\n<iframe loading=\"lazy\" title=\"LeetCode DP\u7ec8\u6781\u5b66\u4e60\u8ba1\u5212\uff01Day1-3\" width=\"500\" height=\"281\" src=\"https:\/\/www.youtube.com\/embed\/LG0adDNnnYg?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>Day 1<\/strong><\/h2>\n\n\n\n<ul class=\"wp-block-list\"><li>509.\u00a0Fibonacci Number<\/li><\/ul>\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) -> O(1)\nclass Solution:\n  @cache\n  def fib(self, n: int) -> int:\n    return n if n <= 1 else self.fib(n - 1) + self.fib(n - 2)\n<\/pre>\n<\/div><\/div>\n\n\n\n<ul class=\"wp-block-list\"><li>1137.\u00a0N-th Tribonacci Number<\/li><\/ul>\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) -> O(1)\nclass Solution:\n  @cache\n  def tribonacci(self, n: int) -> int:\n    if n == 0: return 0\n    if n <= 2: return 1\n    return sum(self.tribonacci(n - i - 1) for i in range(3))\n<\/pre>\n<\/div><\/div>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Day 2<\/strong><\/h2>\n\n\n\n<ul class=\"wp-block-list\"><li>70.\u00a0Climbing Stairs<\/li><\/ul>\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) -> O(1)\nclass Solution:\n  @cache\n  def climbStairs(self, n: int) -> int:\n    if n <= 1: return 1\n    return self.climbStairs(n - 1) + self.climbStairs(n - 2)\n<\/pre>\n<\/div><\/div>\n\n\n\n<ul class=\"wp-block-list\"><li>746.\u00a0Min Cost Climbing Stairs<\/li><\/ul>\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) -> O(1)\nclass Solution:\n  def minCostClimbingStairs(self, cost: List[int]) -> int:\n    @cache\n    def dp(i: int) -> int:\n      if i <= 1: return 0\n      return min(dp(i - 1) + cost[i - 1],\n                 dp(i - 2) + cost[i - 2])\n    return dp(len(cost))\n<\/pre>\n<\/div><\/div>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Day 3<\/strong><\/h2>\n\n\n\n<ul class=\"wp-block-list\"><li>198.\u00a0House Robber<\/li><\/ul>\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) -> O(1)\nclass Solution:  \n  def rob(self, nums: List[int]) -> int:\n    @cache\n    def dp(i: int) -> int:\n      if i < 0: return 0\n      return max(nums[i] + dp(i - 2), dp(i - 1))\n    return dp(len(nums) - 1)\n<\/pre>\n<\/div><\/div>\n\n\n\n<ul class=\"wp-block-list\"><li>213.\u00a0House Robber II<\/li><\/ul>\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) -> O(1)\nclass Solution:\n  def rob(self, nums: List[int]) -> int:\n    n = len(nums)\n    if n == 1: return nums[0]\n\n    @cache\n    def dp(i: int, j: int) -> int:\n      if j < i: return 0\n      return max(nums[j] + dp(i, j - 2), dp(i, j - 1))\n\n    return max(dp(0, n - 2), dp(1, n - 1))\n<\/pre>\n<\/div><\/div>\n\n\n\n<ul class=\"wp-block-list\"><li>740.\u00a0Delete and Earn<\/li><\/ul>\n\n\n\n<p>This problem can be reduced to LC 198 House Robber<\/p>\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(m + n)\n# Space complexity: O(m + n)\nclass Solution:\n  def deleteAndEarn(self, nums: List[int]) -> int:\n    houses = [0] * (10**4 + 1)\n    for x in nums:\n      houses[x] += x\n    \n    @cache\n    def dp(i : int) -> int:\n      if i < 0: return 0\n      return max(houses[i] + dp(i - 2), dp(i - 1))\n    \n    return dp(len(houses) - 1)\n<\/pre>\n<\/div><\/div>\n\n\n\n<p><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Day 1 509.\u00a0Fibonacci Number # Author: Huahua # Time complexity: O(n) # Space complexity: O(n) -> O(1) class Solution: @cache def fib(self, n: int) ->&#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":[740,18],"class_list":["post-8943","post","type-post","status-publish","format-standard","hentry","category-dynamic-programming","tag-coding-with-me","tag-dp","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8943","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=8943"}],"version-history":[{"count":4,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8943\/revisions"}],"predecessor-version":[{"id":8950,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8943\/revisions\/8950"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=8943"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=8943"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=8943"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}