dp Archives - Page 4 of 43 - Huahua's Tech Road

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

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

Posts tagged as “dp”

花花酱 LeetCode Ultimate DP Study Plan Day 9

139. Word Break

Python3

Optimization

Python3

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

1014. Best Sightseeing Pair

Python3

121. Best Time to Buy and Sell Stock

Python3

122. Best Time to Buy and Sell Stock II

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