dp – Page 5 – Huahua’s Tech Road

花花酱 LeetCode Ultimate DP Study Plan Day 10

By zxi on December 11, 2021

413. Arithmetic Slices

Python3

# Author: Huahua

# Time complexity: O(n)

# Space complexity: O(n)

class Solution:

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

@cache

def dp(i: int) -> int:

"""Number of arithmetic subarrays end with nums[i]."""

if i < 2: return 0

if nums[i] - nums[i - 1] == nums[i - 1] - nums[i - 2]:

return 1 + dp(i - 1)

return 0

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

91. Decode Ways

Python3

# Author: Huahua

# Time complexity: O(n^2) -> O(n)

# Space complexity: O(n)

class Solution:

@cache

def numDecodings(self, s: str) -> int:

if not s: return 1

if s[0] == '0': return 0

ans = self.numDecodings(s[1:])

if len(s) > 1 and (s[0] == '1' or (s[0] == '2' and s[1] <= '6')):

ans += self.numDecodings(s[2:])

return ans

花花酱 LeetCode Ultimate DP Study Plan Day 9

By zxi on December 11, 2021

139. Word Break

Python3

# Author: Huahua

# Time complexity: O(n^2)

# Space complexity: O(n^2)

class Solution:

def wordBreak(self, s: str, wordDict: List[str]) -> bool:

words = set(wordDict)

n = len(s)

@cache

def dp(s: str) -> bool:

"""Returns whether s is breakable."""

if not s: return True

for l in range(1, min(n, 20) + 1):

if s[0:l] in words and dp(s[l:]): return True

return dp(s)

Optimization

Python3

# Author: Huahua

# Time complexity: O(n*l^2)

# Space complexity: O(n)

class Solution:

def wordBreak(self, s: str, wordDict: List[str]) -> bool:

words = set(wordDict)

n = len(s)

@cache

def dp(i: int) -> bool:

"""Returns whether s[i:] is breakable."""

if i >= n: return True

for l in range(1, min(n, 20) + 1):

if s[i:i+l] in words and dp(i + l): return True

return dp(0)

花花酱 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 7

By zxi on December 5, 2021

1014. Best Sightseeing Pair

Python3

# Author: Huahua

# Time complexity: O(n)

# Space complexity: O(n)

class Solution:

def maxScoreSightseeingPair(self, values: List[int]) -> int:

# score = (values[i] + i) + (values[j] - j)

@cache

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

"""Returns:

1) Max score of values[0..j]

2) Largest values[i] + i (i <= j)."""

if j < 0: return 0, 0

s, v = dp(j - 1)

return max(s, v + values[j] - j), max(v, values[j] + j)

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

121. Best Time to Buy and Sell Stock

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]:

"""Returns:

1) max profit of prices[0:i].

2) min price of prices[0:i]."""

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

max_profit, min_price = dp(i - 1)

return max(max_profit, prices[i] - min_price), min(min_price, prices[i])

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

122. Best Time to Buy and Sell Stock II

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]:

"""Returns:

1) Max profit after i-th day. Holding no stocks. Can buy.

2) Max balance after i-th day. Holding a stock. Can sell.

"""

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

profit, balance = dp(i - 1)

return (max(profit, balance + prices[i]), # do nothing, sell

max(balance, profit - 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)))

Posts tagged as “dp”

Python3

Python3

Python3

Optimization

Python3

309. Best Time to Buy and Sell Stock with Cooldown

Python3

714 Best Time to Buy and Sell Stock with Transaction Fee

Python3

1014. Best Sightseeing Pair

Python3

121. Best Time to Buy and Sell Stock

Python3

122. Best Time to Buy and Sell Stock II

Python3

152. Maximum Product Subarray

Python3

1567. Maximum Length of Subarray With Positive Product

Python3