EASIEST JAVA SOLUTION EVER !!! (Recursive + Memoized + Tabulation ) All 3 Approaches !!!
Intuition\n\n- This problem is just a variation of LIS(Longest Increasing Subsequence).\n- Here we just have to find the LIS and LDS of the given array.\n- Simi
# Intuition\n\n- This problem is just a variation of LIS(Longest Increasing Subsequence).\n- Here we just have to find the LIS and LDS of the given array.\n- Similarly, in LIS we find the maximum length of the Increasing SubSequence.\n- Here we simply need to find the total number of Increasing and Decreasing Subsequences with length 3.\n\n# Approach\n**Recursive Approach**\n\n# Code\n```\nclass Solution {\n\n    public static int helper2(int[] rating, int ind, int prev, int count){\n\n        if(count == 0){\n            return 1;\n        }\n\n        if(ind == rating.length){\n            return 0;\n        }\n\n        int notPick = helper2(rating, ind+1, prev, count);\n\n        int pick = 0;\n\n        if(prev == -1 || rating[ind]<rating[prev]){\n            pick = helper2(rating, ind+1, ind, count-1);\n        }\n\n        return pick + notPick;\n\n    }\n\n    public static int helper1(int[] rating, int ind, int prev, int count){\n\n        if(count == 0){\n            return 1;\n        }\n\n        if(ind == rating.length){\n            return 0;\n        }\n\n        int notPick = helper1(rating, ind+1, prev, count);\n\n        int pick = 0;\n\n        if(prev == -1 || rating[ind]>rating[prev]){\n            pick = helper1(rating, ind+1, ind, count-1);\n        }\n\n        return pick + notPick;\n\n    }\n\n    public int numTeams(int[] rating) {\n        \n        int ans1 = helper1(rating, 0, -1, 3);\n\n        int ans2 = helper2(rating, 0, -1, 3);\n\n        return ans1+ans2;\n\n    }\n\n}\n```\n\n\n# Approach\n**Recursive + Memoized (Top Down) Approach**\n\n# Code\n```\nclass Solution {\n\n    public static int helper2(int[] rating, int ind, int prev, int count){\n\n        if(count == 0){\n            return 1;\n        }\n\n        if(ind == rating.length){\n            return 0;\n        }\n\n        if(dp2[ind][prev+1][count]!=null){\n            return dp2[ind][prev+1][count];\n        }\n\n        int notPick = helper2(rating, ind+1, prev, count);\n\n        int pick = 0;\n\n        if(prev == -1 || rating[ind]<rating[prev]){\n            pick = helper2(rating, ind+1, ind, count-1);\n        }\n\n        return dp2[ind][prev+1][count] = pick + notPick;\n\n    }\n\n    public static int helper1(int[] rating, int ind, int prev, int count){\n\n        if(count == 0){\n            return 1;\n        }\n\n        if(ind == rating.length){\n            return 0;\n        }\n\n        if(dp1[ind][prev+1][count]!=null){\n            return dp1[ind][prev+1][count];\n        }\n\n        int notPick = helper1(rating, ind+1, prev, count);\n\n        int pick = 0;\n\n        if(prev == -1 || rating[ind]>rating[prev]){\n            pick = helper1(rating, ind+1, ind, count-1);\n        }\n\n        return dp1[ind][prev+1][count] = pick + notPick;\n\n    }\n\n    public static Integer[][][] dp1;\n\n    public static Integer[][][] dp2;\n\n    public int numTeams(int[] rating) {\n\n        dp1 = new Integer[rating.length][rating.length+1][4];\n        \n        int ans1 = helper1(rating, 0, -1, 3);\n\n        dp2 = new Integer[rating.length][rating.length+1][4];\n\n        int ans2 = helper2(rating, 0, -1, 3);\n\n        return ans1+ans2;\n\n    }\n\n}\n```\n\n# Approach\n**Tabulation (Bottom Up) Approach**\n\n# Code\n```\nclass Solution {\n    \n\tpublic int numTeams(int [] rating) {\n\n\t\tint length = rating.length;\n\n\t\tint [] dp = new int[length];\n\n\t\tint count = 0;\n\n\t\tfor (int i=0; i<length; i++) {\n\t\t\tfor (int j=i; j>=0; j--) {\n\t\t\t\tif (rating[i] < rating[j]) {\n\t\t\t\t\tdp[i] += 1;\n\t\t\t\t\tcount += dp[j];\n\t\t\t\t}\n\t\t\t}\n\t\t}\n\n\t\tdp = new int[length];\n\n\t\tfor (int i=0; i<length; i++) {\n\t\t\tfor (int j=i; j>=0; j--) {\n\t\t\t\tif (rating[i] > rating[j]) {\n\t\t\t\t\tdp[i] += 1;\n\t\t\t\t\tcount += dp[j];\n\t\t\t\t}\n\t\t\t}\n\t\t}\n\n\t\treturn count;\n\n    }\n\n}\n```\n
['Dynamic Programming', 'Recursion', 'Memoization', 'Java']