# Facebook

'''

Given the root node of a binary search tree and two integers low and high, return the sum of values of all nodes with a value in the inclusive range [low, high].

Example 1: 

    10
   / \
  5   15
 / \   \
3  7   18


Input: root = [10,5,15,3,7,null,18], low = 7, high = 15

Output: 32


Example 2:

      10
     / \
    5   15
   / \  / \
  3  7 13 18
 / \
1  6

Input: root = [10,5,15,3,7,13,18,1,null,6], low = 6, high = 10
Output: 23


Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.

Eample 1:

Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]

Example 2:

Input: intervals = [[1,4],[4,5]]
Output: [[1,5]]


'''

## 983. Minimum Cost For Tickets

class Solution:
    def backtracking(self, idx, days, costs):
        if idx >= len(days):
            return 0
        
        if idx in self.dp:
            return self.dp[idx]
        
        ans = float('inf')
        for i, x in enumerate(costs):
            if i == 0:
                ans = min(ans, self.backtracking(idx+1, days, costs) + x)
            elif i == 1:
                d = days[idx] + 7
                if d > days[-1]:
                    ans = min(ans, x)
                else:
                    for j in range(idx, len(days)):
                        if days[j] >= d:
                            ans = min(ans, self.backtracking(j, days, costs) + x)
                            break
            elif i == 2:
                d = days[idx] + 30
                if d > days[-1]:
                    ans = min(ans, x)
                else:
                    for j in range(idx, len(days)):
                        if days[j] >= d:
                            ans = min(ans, self.backtracking(j, days, costs) + x)
                            break
        
        self.dp[idx] = ans
        
        return self.dp[idx]
                
        
    def mincostTickets(self, days: List[int], costs: List[int]) -> int:
        self.dp = defaultdict(int)
        return self.backtracking(0, days, costs)

## Combination Sum

https://leetcode.com/problems/combination-sum/

# input: candidates = [2,3,6,7], target = 7
# output: [[2,2,3],[7]]
# my output: [[2,2,3],[2,2,3],[2,2,3],[2,2,3],[7]]

class Solution:
    def backtracking(self, index, sum_, l):
        if index >= len(self.candidates):
            return
        
        if sum_ == self.target:
            self.rst.append(l[:])
            return
            
        if sum_ > self.target:
            return
        
        sum_ += self.candidates[index]
        l.append(self.candidates[index])
        self.backtracking(index, sum_, l)
        self.backtracking(index + 1, sum_, l)
        sum_ -= self.candidates[index]
        l.pop()
        
        self.backtracking(index+1, sum_, l)
        
        
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        self.rst = []
        self.candidates = candidates
        self.target = target
        self.backtracking(0, 0, [])
        
        return self.rst

## 98. Validate Binary Search Tree

https://leetcode.com/problems/validate-binary-search-tree/
(UGLY)

class Solution:
    def dfs(self, root):
        if root:
            left_max = root.val - 1
            right_min = root.val + 1
            right_max = float('-inf')
            left_min = float('inf')
            
            if root.left:
                left_max, left_min = self.dfs(root.left)
                if self.rst == False:
                    return -1, -1
            if root.right:
                right_max, right_min = self.dfs(root.right)
                if self.rst == False:
                    return -1, -1
            
            if not (left_max < root.val < right_min):
                self.rst = False
            
            return (max(left_max, right_max, root.val), min(left_min, right_min, root.val))
    
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        self.rst = True
        self.dfs(root)
        
        return self.rst

:::danger

:::

## 516. Longest Palindromic Subsequence

from collections import defaultdict

class Solution:
    def longestPalindromeSubseqHelper(self, s, l, r, cnt):
        if l == r:
            return cnt+1
        
        if l > r:
            return cnt
        
        if (l,r) in self.dp:
            return self.dp[(l,r)]
        
        if s[l] == s[r]:
            self.dp[(l,r)] = self.longestPalindromeSubseqHelper(s, l+1, r-1, cnt + 2)
        else:
            self.dp[(l,r)] = max(self.longestPalindromeSubseqHelper(s, l+1, r, cnt), self.longestPalindromeSubseqHelper(s, l, r-1, cnt))
        
        return self.dp[(l,r)]
        
    def longestPalindromeSubseq(self, s: str) -> int:
        self.dp = defaultdict(lambda:0)
        self.longestPalindromeSubseqHelper(s, 0, len(s)-1, 0)
        print(self.dp)
        return self.dp[(0, len(s)-1)]