Detailed explanation DP | Python | From "why" to "how"
I have used the bottom up approach for this problem. I will skip the introduction to the bottom up approach itself and focus more on how one should have guessed
I have used the bottom up approach for this problem. I will skip the introduction to the bottom up approach itself and focus more on how one should have guessed how to implement it. You should easily follow my thought flow and replicate it in other similar problems.\n\nIt is trivial that we would like to build something like dp[i][j] where i is the size of the team and j is something related to the number of available solders. Similar to famous 1/0 knapsack problem. But what exactly my our dp[i][j] would represent? \n\nIn order to answer the question in hand, let\'s have a look at the given example:\nrating = [2,5,3,4,1]\n\nFor now I will only describe the type of teams with increasing raknings for simplicity of the concept. Later we will easily expand it to decreasing rankings as well. let\'s consider that we have solders [2,5,3]. It\'s easy to show that all possible teams of size 2 are the following:\n2 5\n2 3\nIn the next step of dynamically calculating our dp we allow having another solder and our troop becomes [2,5,3,4]. Analysing the teams of 2 people and knowing that the rank of the next solder is 4 we can notice that we only care about the rank of the last person in the team to know whether we can make a group of 3 adding our next solder.\n2 **5**  4 (not possible to form)\n2 **3**  4 (possible to form)\nLet me repeat that again, we do not care about what ranks come before the last person in the team. We only care about 5 and 3 in our example. \n\nSo this gives us a hint that our dp[i][j] should have information about the number of groups of size i that ends with a person at j-th rank.\n\nNow let\'s think about what initial case we should start from. If we look at the dp[1][j] that is the number of groups of size 1 that can be created with the last person of rank j we can easily see that for each element there is only one possible team that includes the solder (him/her)self. So we can initialize our dp[1][j] = 1 for all j and starting from that dynamically calculate the number of teams that can be formed ending with solder j.\n\nPseudocode for dynamically calculating dp:\n```\niterate over size of teams from 1 to 3: (iterator i)\n\titerate over each solder: (iterator j)\n\t\titerate over each solder with lower index: (iterator k)\n\t\t\tif rank of solder > rank of solder with lower index: \n\t\t\t\tdp_inc[i][j] += dp_inc[i-1][k] # for increasing ranking\n\t\t\telse:\n\t\t\t\tdp_dec[i][j] += dp_dec[i-1][k] # for decreasing ranking\n```\t\t\t\t\nIn the end, after calculating dp_inc[3] and dp_dec[3] they both include the information about the number of teams of size 3 that can be created ending with the solder with index j. By summing up all possible number of teams we arrive to the needed output.\n\nThe compele solution:\n```\nclass Solution:\n    def numTeams(self, rating: List[int]) -> int:\n        n = len(rating)\n        dp_inc = [[0] * n for i in range(4)] \n        dp_dec = [[0] * n for i in range(4)]\n        for i in range(n):\n            dp_inc[1][i] = 1\n            dp_dec[1][i] = 1\n        for i in range(2, 4):\n            for j in range(n):\n                for k in range(j):\n                    if rating[j] > rating[k]:\n                        dp_inc[i][j] += dp_inc[i-1][k]\n                    else:\n                        dp_dec[i][j] += dp_dec[i-1][k]\n        return sum(dp_inc[3]) + sum(dp_dec[3])\n        \n```
['Dynamic Programming']