Python | O(n^2) | Slow but very easy to understand | Explanation
dp[i] is a 3-tuple which indicates the number of teams of size 1, 2, 3 respectively ending with index i\n So, dp is n * 3 matrix. Initialize dp[i] to be [1, 0, 
* dp[i] is a 3-tuple which indicates the number of teams of size 1, 2, 3 respectively ending with index i\n* So, dp is n * 3 matrix. Initialize dp[i] to be [1, 0, 0] because there is only one team with size 1 ending with index i (which is just the team with only index i)\n* Now, for each index i, loop through all indices j from 0 to i - 1 and compare each element to rating[i]. If an element is smaller than rating[i] then that means we can form a team of size 3 with all the teams of size 2 ending with j and we can form a team of size 2 with all teams of size 1 ending with j.\n* The reason we are interested in storing teams of size 1, 2 is because we want to carry the partial solution forward so that we can avoid an extra for loop.\n* Now just add all the teams of size 3 and perform the same nested loops but this time in comparison check for elements larger than rating[i].\n* Let me know in the comments if you have any questions.\n```\nclass Solution:\n    def numTeams(self, rating: List[int]) -> int:\n        \n        dp = [[1, 0, 0] for i in range(len(rating))]\n        \n        for i in range(1, len(rating)):\n            for j in range(i):\n                if rating[i] > rating[j]:\n                    dp[i][1] += dp[j][0]\n                    dp[i][2] += dp[j][1]\n        \n        a = sum(dp[i][2] for i in range(len(dp)))\n        #print(a)\n\n        dp = [[1, 0, 0] for i in range(len(rating))]\n        \n        for i in range(1, len(rating)):\n            for j in range(i):\n                if rating[i] < rating[j]:\n                    dp[i][1] += dp[j][0]\n                    dp[i][2] += dp[j][1]\n        \n        b = sum(dp[i][2] for i in range(len(dp)))\n        \n        return a + b
['Dynamic Programming', 'Python', 'Python3']