Dynamic Programming

Challenge You are given an integer array called nums, your task is to return the longest increasing subsequence. E.g [0,1,2,7] is the longest subsequence of the array [0,3,1,6,2,2,7] Solution 1 - Recursion class Solution: def first_solution(self, nums, index, prev, ct): if index > len(nums): self.m = max(self.m, ct) return self.first_solution(nums, index + 1, prev, ct) if index < len(nums) and nums[index] > prev: self.first_solution(nums, index + 1, nums[index], ct + 1) return ct def lengthOfLIS(self, nums: List[int]) -> int: self.m = 0 self.first_solution(tuple(nums), 0, float("-inf"), 0) return self.m Time complexity: O(n^2) ...

Challenge The array nums represent the value inside each house. What is stopping you to rob everything is that you cannot rob two consecutive houses without triggering the alarm. Determine the maxium amout of money you can rob without triggering the alarm. Solution 1 - Recursion class Solution: def helper(self, index, nums, val): if index > len(nums)-1: self.m = max(self.m, val) return self.helper(index+1, nums, val) self.helper(index+2, nums, nums[index] + val) def rob(self, nums: List[int]) -> int: self.m = float("-inf") self.helper(0, nums, 0) return self.m Time Complexity: O(2^n) ...

Challenge Given a rod of length N. You are also given an array that represents the revenue of each cut size. You want to maximize revenue. E.g : [2,3,7,8], piece of length 1 gets you 2$. Solution Top down with Memoization: class Solution: def helper(self, n, cost): if n < 0: return 0 if n == 0: return cost if n in self.memo: return self.memo[n] res = 0 for i in range(1, len(self.cost)+1): res = max(res, self.helper(n-i, cost + self.cost[i])) self.memo[n] = res return self.memo[n] def rodCutting(self, n, cuts): self.res = 0 self.memo = {} cost = {} for i, e in enumerate(cuts): cost[i+1] = e self.cost = cost return self.helper(n, 0)

Challenge Your task is to print the Nth catalan number. catalan(5) = 42 Solution Bottom up def catalan(n): res = [0 for i in range(n+1)] res[0] = 1 s = 0 for i in range(1, n+1): for j in range(0, i): res[i] += res[j] * res[i-j-1] return res[n] Time Complexity: O(n^2) Top Down def catalan(n): if n == 0 or n ==1: return 1 s = 0 for i in range(n): s += catalan(i) * catalan(n-1-i) return s Time Complexity: O(n!) Application Find the number of unique BST.