Understanding the pattern | Java Solution | Recursion + Memoization
I wanted to solve binary search + dp problems and was looking for similar patterns.\nAfter few hours of grilling and understanding patterns  between \nhttps://l
I wanted to solve binary search + dp problems and was looking for similar patterns.\nAfter few hours of grilling and understanding patterns  between \nhttps://leetcode.com/problems/maximum-number-of-events-that-can-be-attended-ii/\nhttps://leetcode.com/problems/two-best-non-overlapping-events/\nhttps://leetcode.com/problems/maximum-profit-in-job-scheduling/\nWill add more problems to this template\n\nI came up with following template -\nSolution for https://leetcode.com/problems/maximum-number-of-events-that-can-be-attended-ii/\n```\nclass Solution {\n    public int maxValue(int[][] events, int k) {\n        //here k is optional maximum capacity of like knapsack \n int n=events.length;\n      \n       Arrays.sort(events, (a, b) ->  Integer.compare(a[0], b[0]) );\n        Integer[][] dp=new Integer[n][k];\n        return dfs(events,0,0,n,k,dp);\n    }\n    \n    public int dfs(int[][] events, int idx,int choose, int n,int k,Integer[][] dp){\n        if(idx>=n)return 0;\n        if(choose>=k)return 0;\n        if(dp[idx][choose]!=null)return dp[idx][choose];\n        int nextIdx=findNext(events, idx,n);\n        int pick=events[idx][2]+dfs(events, nextIdx,choose+1, n,k,dp);\n        int notPick=dfs(events, idx+1,choose, n,k,dp);\n        return dp[idx][choose]= Math.max(pick,notPick);\n    }\n    public int findNext(int[][] events, int idx, int n){\n        int ans=n;\n        int l=idx+1;\n        int r=n-1;\n        while(l<=r){\n            int mid=l+(r-l)/2;\n            if(events[idx][1]<events[mid][0]){\n                ans=mid;\n                r=mid-1;\n            }else {\n                l=mid+1;\n            }\n        }\n        return ans;\n    }\n}\n```\n\nFor https://leetcode.com/problems/two-best-non-overlapping-events/ k=2\n\n```\n int n=events.length;\n      \n       Arrays.sort(events, (a, b) ->  Integer.compare(a[0], b[0]) );\n        Integer[][] dp=new Integer[n][k];\n        return dfs(events,0,0,n,k,dp);\n    }\n    \n    public int dfs(int[][] events, int idx,int choose, int n,int k,Integer[][] dp){\n        if(idx>=n)return 0;\n        if(choose>=k)return 0;\n        if(dp[idx][choose]!=null)return dp[idx][choose];\n        int nextIdx=findNext(events, idx,n);\n        int pick=events[idx][2]+dfs(events, nextIdx,choose+1, n,k,dp);\n        int notPick=dfs(events, idx+1,choose, n,k,dp);\n        return dp[idx][choose]= Math.max(pick,notPick);\n    }\n    public int findNext(int[][] events, int idx, int n){\n        int ans=n;\n        int l=idx+1;\n        int r=n-1;\n        while(l<=r){\n            int mid=l+(r-l)/2;\n            if(events[idx][1]<events[mid][0]){\n                ans=mid;\n                r=mid-1;\n            }else {\n                l=mid+1;\n            }\n        }\n        return ans;\n    }\n}\n```\n\nThere may be condition when no k boundation is required for example in question https://leetcode.com/problems/maximum-profit-in-job-scheduling/\n\n```\nclass Solution {\n    public int jobScheduling(int[] startTime, int[] endTime, int[] profit) {\n        int n=startTime.length;\n        int[][] events=new int[n][3];\n        for(int i=0;i<n;i++){\n            events[i][0]=startTime[i];\n            events[i][1]=endTime[i];\n            events[i][2]=profit[i];\n        }\n        Arrays.sort(events,(a,b)->Integer.compare(a[0], b[0]));\n        Integer[] dp=new Integer[n];\n        return dfs(events,0,n,dp);\n    }\n    \n    public int dfs(int[][] events, int idx, int n,Integer[] dp){\n        if(idx==n)return 0;\n        if(dp[idx]!=null)return dp[idx];\n        int nextIdx=findNext(events, idx,n);\n        int pick=events[idx][2]+dfs(events, nextIdx, n,dp);\n        int notPick=dfs(events, idx+1, n,dp);\n        return dp[idx]= Math.max(pick,notPick);\n    }\n    public int findNext(int[][] events, int idx, int n){\n        int ans=n;\n        int l=idx+1;\n        int r=n-1;\n        while(l<=r){\n            int mid=(l+r)>>1;\n            if(events[idx][1]<=events[mid][0]){\n                ans=mid;\n                r=mid-1;\n            }else {\n                l=mid+1;\n            }\n        }\n        return ans;\n    }\n}\n```
['Dynamic Programming', 'Recursion', 'Memoization', 'Binary Tree', 'Java']