coding with me Archives - Huahua's Tech Road

花花酱 LeetCode Ultimate DP Study Plan Day 8

By zxi on December 9, 2021

309. Best Time to Buy and Sell Stock with Cooldown

Python3

# Author: Huahua

# Time complexity: O(n)

# Space complexity: O(n)

class Solution:

def maxProfit(self, prices: List[int]) -> int:

@cache

def dp(i: int) -> Tuple[int, int, int]:

"""

Returns

1) sold: Max profit w/o holdings. Can't buy. Can't sell.

2) holding: Max profit w/ holdings. Can't buy, Can sell.

3) cooldown: Max profit w/o holdings. Can buy. Can't sell."""

if i < 0: return -10**9, -10**9, 0

sold, holding, cooldown = dp(i - 1)

return (holding + prices[i], # sold

max(holding, cooldown - prices[i]), # do nothing, or buy.

max(cooldown, sold)) # cooldown

return max(dp(len(prices) - 1))

714 Best Time to Buy and Sell Stock with Transaction Fee

Python3

# Author: Huahua

# Time complexity: O(n)

# Space complexity: O(n)

class Solution:

def maxProfit(self, prices: List[int], fee: int) -> int:

@cache

def dp(i: int) -> Tuple[int, int]:

"""

Returns:

1) sold: Max profit w/o holdings.

2) holding: Max profit w/ holdings."""

if i < 0: return 0, -10**9

sold, holding = dp(i - 1)

return (max(sold, holding + prices[i] - fee), # do nothing, sell

max(holding, sold - prices[i])) # do nothing, buy

return dp(len(prices) - 1)[0]

花花酱 LeetCode Ultimate DP Study Plan Day 6

By zxi on December 1, 2021

152. Maximum Product Subarray

Python3

# Author: Huahua

# Time complexity: O(n)

# Space complexity: O(n) -> O(1)

class Solution:

def maxProduct(self, nums: List[int]) -> int:

@cache

def dp(i: int) -> Tuple[int, int]:

"""min / max subarray product ends with nums[i]."""

if i == 0: return nums[i], nums[i]

low, hi = dp(i - 1)

if nums[i] < 0: low, hi = hi, low

return min(low * nums[i], nums[i]), max(hi * nums[i], nums[i])

return max(dp(i)[1] for i in range(len(nums)))

1567. Maximum Length of Subarray With Positive Product

Python3

# Author: Huahua

# Time complexity: O(n)

# Space complexity: O(n) -> O(1)

class Solution:

def getMaxLen(self, nums: List[int]) -> int:

@cache

def dp(i: int) -> Tuple[int, int]:

"""Max length of pos/neg product ends with nums[i]."""

if i < 0 or nums[i] == 0: return 0, 0

p, n = dp(i - 1)

if nums[i] > 0:

return p + 1, n + 1 if n else 0

else: # nums[i] < 0

return n + 1 if n else 0, p + 1

return max(dp(i)[0] for i in range(len(nums)))

花花酱 LeetCode Ultimate DP Study Plan Day 5

By zxi on December 1, 2021

53. Maximum Subarray

Python3

# Author: Huahua

# Time complexity: O(n)

# Space complexity: O(n)

class Solution:

def maxSubArray(self, nums: List[int]) -> int:

@cache

def dp(i: int) -> int:

"""Max subarray ends with nums[i]."""

if i < 0: return 0 # Empty array.

return nums[i] + max(0, dp(i - 1))

# Try all possible ending positions.

return max(dp(i) for i in range(len(nums)))

918. Maximum Sum Circular Subarray

Python3

# Author: Huahua

# Time complexity: O(n)

# Space complexity: O(n)

class Solution:

def maxSubarraySumCircular(self, nums: List[int]) -> int:

n = len(nums)

@cache

def dp(i: int, s: int) -> int:

"""Max subarray ends with s * nums[i]."""

if i < 0: return 0 # Empty array.

# Append to max subbary ends with nums[i-1] or start a new one.

return nums[i] * s + max(0, dp(i - 1, s))

max_p = max(dp(i, 1) for i in range(n))

max_n = max(dp(i, -1) for i in range(n))

return max_p if max_p < 0 else max(max_p, sum(nums) + max_n)

花花酱 LeetCode Ultimate DP Study Plan Day 4

By zxi on December 1, 2021

55 Jump Game

Python3

# Author: Huahua

# Time complexity: O(n^2)

# Space complexity: O(n)

class Solution:

def canJump(self, nums: List[int]) -> bool:

n = len(nums)

@cache

def dp(i: int) -> bool:

"""Returns whether we can reach n - 1 from i."""

if i >= n - 1: return True

if i + nums[i] >= n - 1: return True

for s in range(1, nums[i] + 1):

if dp(i + s): return True

return False

return dp(0)

45 Jump Game II

Python3

# Author: Huahua

# Time complexity: O(n^2)

# Space complexity: O(n)

class Solution:

def jump(self, nums: List[int]) -> int:

n = len(nums)

@cache

def dp(i: int) -> int:

"""Min steps to reach n - 1 from i."""

if i >= n - 1: return 0

if i + nums[i] >= n - 1: return 1

ans = n

for s in range(1, nums[i] + 1):

ans = min(ans, dp(i + s) + 1)

return ans

return dp(0)

花花酱 LeetCode Ultimate DP Study Plan Day 1 – 3

By zxi on November 30, 2021

Day 1

509. Fibonacci Number

Python3

# Author: Huahua

# Time complexity: O(n)

# Space complexity: O(n) -> O(1)

class Solution:

@cache

def fib(self, n: int) -> int:

return n if n <= 1 else self.fib(n - 1) + self.fib(n - 2)

1137. N-th Tribonacci Number

Python3

# Author: Huahua

# Time complexity: O(n)

# Space complexity: O(n) -> O(1)

class Solution:

@cache

def tribonacci(self, n: int) -> int:

if n == 0: return 0

if n <= 2: return 1

return sum(self.tribonacci(n - i - 1) for i in range(3))

Day 2

70. Climbing Stairs

Python3

# Author: Huahua

# Time complexity: O(n)

# Space complexity: O(n) -> O(1)

class Solution:

@cache

def climbStairs(self, n: int) -> int:

if n <= 1: return 1

return self.climbStairs(n - 1) + self.climbStairs(n - 2)

746. Min Cost Climbing Stairs

Python3

# Author: Huahua

# Time complexity: O(n)

# Space complexity: O(n) -> O(1)

class Solution:

def minCostClimbingStairs(self, cost: List[int]) -> int:

@cache

def dp(i: int) -> int:

if i <= 1: return 0

return min(dp(i - 1) + cost[i - 1],

dp(i - 2) + cost[i - 2])

return dp(len(cost))

Day 3

198. House Robber

Python3

# Author: Huahua

# Time complexity: O(n)

# Space complexity: O(n) -> O(1)

class Solution:

def rob(self, nums: List[int]) -> int:

@cache

def dp(i: int) -> int:

if i < 0: return 0

return max(nums[i] + dp(i - 2), dp(i - 1))

return dp(len(nums) - 1)

213. House Robber II

Python3

# Author: Huahua

# Time complexity: O(n)

# Space complexity: O(n) -> O(1)

class Solution:

def rob(self, nums: List[int]) -> int:

n = len(nums)

if n == 1: return nums[0]

@cache

def dp(i: int, j: int) -> int:

if j < i: return 0

return max(nums[j] + dp(i, j - 2), dp(i, j - 1))

return max(dp(0, n - 2), dp(1, n - 1))

740. Delete and Earn

This problem can be reduced to LC 198 House Robber

Python3

# Author: Huahua

# Time complexity: O(m + n)

# Space complexity: O(m + n)

class Solution:

def deleteAndEarn(self, nums: List[int]) -> int:

houses = [0] * (10**4 + 1)

for x in nums:

houses[x] += x

@cache

def dp(i : int) -> int:

if i < 0: return 0

return max(houses[i] + dp(i - 2), dp(i - 1))

return dp(len(houses) - 1)

Posts tagged as “coding with me”

花花酱 LeetCode Ultimate DP Study Plan Day 8

309. Best Time to Buy and Sell Stock with Cooldown

Python3

714 Best Time to Buy and Sell Stock with Transaction Fee

Python3

花花酱 LeetCode Ultimate DP Study Plan Day 6

152. Maximum Product Subarray

Python3

1567. Maximum Length of Subarray With Positive Product

Python3

花花酱 LeetCode Ultimate DP Study Plan Day 5

53. Maximum Subarray

Python3

918. Maximum Sum Circular Subarray

Python3

花花酱 LeetCode Ultimate DP Study Plan Day 4

55 Jump Game

Python3

45 Jump Game II

Python3

花花酱 LeetCode Ultimate DP Study Plan Day 1 – 3

Day 1

Python3

Python3

Day 2

Python3

Python3

Day 3

Python3

Python3

Python3