```python class Solution: def canPartition(self, nums: List[int]) -> bool: # time O(N_sum) space time O(N_sum) # step1: check if posibble to equal _sum = sum(nums) size = len(nums) if _sum%2 != 0 : return False avg = _sum//2 # dp[i][j]: first i numbers can be summed up to j dp...
[Read More]
887. Super Egg Drop
```python class Solution: def superEggDrop(self, K: int, N: int) -> int: # time O(K*NlgN) space O(KN) # initialize dp[K][N] memo = {} def dp(K,N): # base case if K == 1: return N if N == 0: return 0 if (K,N) in memo: return memo[(K,N)] # make choice res =...
[Read More]
516. Longest Palindromic Subsequence
```python
class Solution:
def longestPalindromeSubseq(self, s: str) -> int:
# time O(N^2) space O(N^2)
#dp[i][j] stands for longest palindrom from s[i:j+1]
[Read More]
509. Fibonacci Number
memo solution time O(N) space O(N)
```python
class Solution:
def fib(self, N: int) -> int:
memo = {}
memo[0] = 0
memo[1] = 1
if N > 1:
for i in range(2,N+1):
memo[i]= memo[i-1]+memo[i-2]
return memo[N]
[Read More]
322. Coin Change
top down LTE ```python class Solution: def coinChange(self, coins: List[int], amount: int) -> int: def dp(n): if n == 0: return 0 if n < 0 : return -1 res = float(‘inf’) for coin in coins: if dp(n-coin) < 0 : continue res = min(res,dp(n-coin)+1) return res if res !=...
[Read More]