Day 1
- 509. Fibonacci Number
Python3
1 2 3 4 5 6 7 |
# 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
1 2 3 4 5 6 7 8 9 |
# 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
1 2 3 4 5 6 7 8 |
# 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
1 2 3 4 5 6 7 8 9 10 11 |
# 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
1 2 3 4 5 6 7 8 9 10 |
# 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
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
# 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
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
# 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) |