class Solution {
    public int maximumScore(int[] nums, int[] multipliers) {
        int n = nums.length, m = multipliers.length;
        int[][] dp = new int[m+1][m+1];
        
        for(int i = 1; i <= m; i++){
            int mul = multipliers[i-1];
            for(int l = 0; l <= i; l++){
                int r = i - l;
                int iL = l - 1, iR = n - r;
                if(l == 0) dp[l][r] = dp[l][r-1] + mul * nums[iR];
                else if(r == 0) dp[l][r] = dp[l-1][r] + mul * nums[iL];
                else dp[l][r] = Math.max(dp[l-1][r] + mul * nums[iL], dp[l][r-1] + mul * nums[iR]);
            }
        }
        int ans = Integer.MIN_VALUE;
        for(int l = 1; l <= m; l++){
            int r = m - l;
            ans = Math.max(ans, dp[l][r]);
        }
        return ans;
    }
}

class Solution {
    public int numFactoredBinaryTrees(int[] arr) {
        final int MOD = (int) Math.pow(10, 9) + 7;
        Arrays.sort(arr);   //from minium to maxium
        HashMap<Integer, Integer> map = new HashMap<>();
        
        for(int i = 0; i < arr.length; i++){
            map.put(arr[i], i);
        }
        
        long[] dp = new long[arr.length];
        Arrays.fill(dp, 1);
        
        for(int i = 0; i < arr.length; i++){
            for(int left = 0; left < i; left++){
                if(arr[i] % arr[left] == 0){   //make sure divisible
                    int k = arr[i] / arr[left];
                    if(map.containsKey(k)){
                        int right = map.get(k);
                        dp[i] = (dp[i] + dp[left] * dp[right]) % MOD; 
                    }
                }
            }
        }
        
        int res = 0;
        
        for(long num : dp){
            res += num;
            res %= MOD;
        }
        
        return (int) res;
    }
}

class Solution {
    final int MOD = (int) Math.pow(10, 9) + 7;
    long[][][] memo;
    public int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {
        memo = new long[m][n][maxMove];
       for(int i = 0; i < m; i++){
           for(int j = 0; j < n; j++){
               for(int k = 0; k < maxMove; k++){
                   memo[i][j][k] = -1;
               }
           }
       }
        return (int) dfs(m, n, maxMove, startRow, startColumn);
    }
    
    private long dfs(int m, int n, int maxMove, int startRow, int startColumn){
        if(startRow < 0 || startRow >= m || startColumn < 0 || startColumn >= n) return 1;
        if(maxMove == 0) return 0;
        
        maxMove--;
        if(memo[startRow][startColumn][maxMove] != -1) return memo[startRow][startColumn][maxMove];
        
        long left = dfs(m, n, maxMove, startRow-1, startColumn);
        long right = dfs(m, n, maxMove, startRow+1, startColumn);
        long up = dfs(m, n, maxMove, startRow, startColumn+1);
        long down = dfs(m, n, maxMove, startRow, startColumn-1);

        memo[startRow][startColumn][maxMove] = (left + right + up + down) % MOD;
        return memo[startRow][startColumn][maxMove];
    }
}

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int[] dp = new int[cost.length+1];
        for(int i = 2; i <= cost.length; i++){
            dp[i] = Math.min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2]);
        }
        return dp[cost.length];
    }
}

class Solution {
    int[] memo;
    public int fib(int n) {
        if(n == 0 || n == 1) return n;
        memo = new int[n+1];
        return fibo(n);
    }
    
    private int fibo(int n){
        if(n == 0 || n == 1) return n;
        if(memo[n] == 0) memo[n] = fibo(n-1) + fibo(n-2);
        return memo[n];
    }
}

class Solution {
    public int fib(int n) {
        if(n == 0 || n == 1) return n;
        return fib(n-1) + fib(n-2);
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    int res = 0; //记录摄像头个数
    public int minCameraCover(TreeNode root) {
        if(judge(root) == 0) res++;  //如果根节点未被监控，则需要增加一个摄像机
        return res;
    }
    public int judge(TreeNode root){
        if(root == null) return 2;   //根节点为空时返回2，这样叶子节点变为未被监控
        int left = judge(root.left);
        int right = judge(root.right);

        if(left == 0 || right == 0){    //如果左右子节点有未被监控的节点，则当前节点设置为摄像机，结果加一，返回1
            res++;
            return 1;
        }
        if(left == 1 || right == 1) return 2;    //如果左右子节点中有摄像机，则当前节点已被监控，返回2
        return 0;   //如果左右子节点都被监控，则当前节点未被监控，返回0
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int minCameraCover(TreeNode root) {
        return Math.min(minCam(root, true, true), minCam(root, false, false));
    }
    
    private int minCam(TreeNode root, boolean hasCamera, boolean isWatched){
        if(root == null) return hasCamera ? Integer.MAX_VALUE / 2 : 0;

        if(hasCamera){
            int min = Math.min(minCam(root.left, false, true) + minCam(root.right, false, true), minCam(root.left, true, true) + minCam(root.right, false, true));
            min = Math.min(min, minCam(root.left, false, true) + minCam(root.right, true, true));
            return 1 + min;
        }
        else if(isWatched){
            int min = Math.min(minCam(root.left, true, true) + minCam(root.right, true, true), minCam(root.left, true, true) + minCam(root.right, false, false));
            min = Math.min(min, minCam(root.left, false, false) + minCam(root.right, true, true));
            min = Math.min(min, minCam(root.left, false, false) + minCam(root.right, false, false));
            return min;
        }
        else{
            int min = Math.min(minCam(root.left, true, true) + minCam(root.right, true, true), minCam(root.left, true, true) + minCam(root.right, false, false));
            min = Math.min(min, minCam(root.left, false, false) + minCam(root.right, true, true));
            return min;
        }
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int minCameraCover(TreeNode root) {
        int[] res = minCam(root);
        return Math.min(res[0], res[2]);
    }
    
    private int[] minCam(TreeNode root){
        if(root == null){
            return new int[] {Integer.MAX_VALUE/2, 0, 0};
        }
        int[] left = minCam(root.left);
        int[] right = minCam(root.right);

        int withCam = 1 + Math.min(left[1] + right[1], Math.min(left[0] + right[1], left[1] + right[0]) );
        int noCamWatchedByParent = Math.min( left[0] + right[0], Math.min( left[0] + right[2], Math.min( left[2] + right[0], left[2] + right[2] )));
        int noCamWatchedBySon = Math.min( left[0] + right[0], Math.min( left[0] + right[2], left[2] + right[0]));
        return new int[] {withCam, noCamWatchedByParent, noCamWatchedBySon};
    }
}

class Solution {
    public int longestStrChain(String[] words) {
        int max = 0;
        Arrays.sort(words, (a,b) -> a.length() - b.length());
        int[] dp = new int[words.length+1];
        for(int i = 1; i <= words.length; i++){
            for(int j = i + 1; j <= words.length; j++){
                if(isValid(words[i-1], words[j-1])){
                    dp[j] = Math.max(dp[j], dp[i] + 1);
                    max = Math.max(max, dp[j]);
                }
            }
        }
        return max + 1;
    }
    
    private boolean isValid(String predecessor, String next){
        if(predecessor.length() + 1 != next.length()) return false;
        boolean flag = true;
        int i = 0, j = 0;
        while(i < next.length() && j < predecessor.length()){
            if(next.charAt(i) == predecessor.charAt(j)){
                i++;
                j++;
            }
            else if(flag){
                i++;
                flag = false;
            }
            else{
                return false;
            }
        }
        return true;
    }
}

class NumMatrix {
    int[][] dp;
    public NumMatrix(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        dp = new int[m+1][n+1];
        
        for(int i = 1; i <= matrix.length; i++){
            for(int j = 1; j <= matrix[0].length; j++){
                dp[i][j] = dp[i][j-1] - dp[i-1][j-1] + dp[i-1][j] + matrix[i-1][j-1];
            }
        };
    }
    
    public int sumRegion(int row1, int col1, int row2, int col2) {
        return dp[row1][col1] + dp[row2+1][col2+1] - dp[row1][col2+1] - dp[row2+1][col1];
    }
}

/**
 * Your NumMatrix object will be instantiated and called as such:
 * NumMatrix obj = new NumMatrix(matrix);
 * int param_1 = obj.sumRegion(row1,col1,row2,col2);
 */

class NumMatrix {
    int[][] mat;
    public NumMatrix(int[][] matrix) {
        mat = matrix;
    }
    
    public int sumRegion(int row1, int col1, int row2, int col2) {
        int sum = 0;
        for(int i = row1; i <= row2; i++){
            for(int j = col1; j <= col2; j++){
                sum += mat[i][j];
            }
        }
        return sum;
    }
}

/**
 * Your NumMatrix object will be instantiated and called as such:
 * NumMatrix obj = new NumMatrix(matrix);
 * int param_1 = obj.sumRegion(row1,col1,row2,col2);
 */

class Solution {
    public int[] runningSum(int[] nums) {
        for(int i = 1; i < nums.length; i++){
            nums[i] += nums[i-1];
        }
        return nums;
    }
}

class Solution {
    public int maxEnvelopes(int[][] envelopes) {
        Arrays.sort(envelopes, (a,b) -> a[0] != b[0] ? a[0] - b[0] : b[1] - a[1]);
        
        List<Integer> arr = new ArrayList<>();
        arr.add(envelopes[0][1]);
        for(int i = 1; i < envelopes.length; i++){
            int height = envelopes[i][1];
            if(height > arr.get(arr.size()-1)){
                arr.add(height);
            }
            else{
                int index = Collections.binarySearch(arr, height);
                if(index < 0) index = -index-1;
                arr.set(index, height);
            }
        }
        return arr.size();
    }
}

class Solution {
    int[][] dolls;
    int[] memo;
    
    public int maxEnvelopes(int[][] envelopes) {
        dolls = envelopes;
        memo = new int[dolls.length];
        int res = 0;
        for(int i = 0; i < dolls.length; i++){
            if(memo[i] != 0) continue;
            memorazation(i);
            res = Math.max(res, memo[i]);
        }
        return res;
    }
    
    private int memorazation(int i){
        if(memo[i] != 0){
            return memo[i];
        }
        int max = 1;
        for(int k = 0; k < dolls.length; k++){
            if(dolls[k][0] < dolls[i][0] && dolls[k][1] < dolls[i][1]){
                max = Math.max(max, memorazation(k) + 1);
            }
        }
        return memo[i] = max;
    }
}

class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        int[][][] dp = new int[strs.length+1][m+1][n+1];
        
        for(int i = 1; i <= strs.length; i++){
            int zeros = 0, ones = 0;
            for(char c : strs[i-1].toCharArray()){
                if(c == '0') zeros++;
                else ones++;
            }
            
            for(int j = 0; j <= m; j++){
                for(int k = 0; k <= n; k++){
                    if(j - zeros >= 0 && k - ones >=0) dp[i][j][k] = Math.max(dp[i-1][j][k], dp[i-1][j-zeros][k-ones] + 1);
                    else dp[i][j][k] = dp[i-1][j][k];
                }
            }
        }
        return dp[strs.length][m][n];
    }
}

class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        int[][] dp = new int[m+1][n+1];
        
        for(String s : strs){   //记录每个位置对应的0和1数量
            int zeros = 0, ones = 0;
            for(char c : s.toCharArray()){
                if(c == '0') zeros++;
                else ones++;
            }
            
            for(int i = m; i >= zeros; i--){
                for(int j = n; j >= ones; j--){
                    dp[i][j] = Math.max(dp[i][j], dp[i-zeros][j-ones] + 1);
                }
            }
        }
        return dp[m][n];
    }
}

class Solution {
    String[] s;
    int[] zeros, ones;
    int[][][] memo;
    public int findMaxForm(String[] strs, int m, int n) {
        s = strs;
        zeros = new int[strs.length];
        ones = new int[strs.length];
        memo = new int[strs.length][m+1][n+1];
        
        for(int i = 0; i < strs.length; i++){   //记录每个位置对应的0和1数量
            for(int j = 0; j < strs[i].length(); j++){
                if(s[i].charAt(j) == '0') zeros[i]++;
                else ones[i]++;
            }
        }
        return dfs(0, m, n);
    }
    
    private int dfs(int i, int zero, int one){
        if(i >= s.length){
            return 0;
        }
        if(memo[i][zero][one] != 0) return memo[i][zero][one];
        
        int maxPossibleSubset = 0;
        
        if(zero-zeros[i] >= 0 && one-ones[i] >= 0){
            maxPossibleSubset = 1 + dfs(i+1, zero-zeros[i], one-ones[i]);
        }
        memo[i][zero][one] = Math.max(maxPossibleSubset, dfs(i+1, zero, one));
        return memo[i][zero][one];
        
    }
}

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        
        int[][] dp = new int[m+1][n+1];
        dp[0][1] = 1;
        
        for(int x = 1; x < m+1; x++){
            for(int y = 1; y < n+1; y++){
                if(obstacleGrid[x-1][y-1] == 0){
                    dp[x][y] = dp[x][y-1] + dp[x-1][y];
                }
            }
        }
        return dp[m][n];
    }
}