Python DP approach (+ some Explanation)
Most of us here are preparing for programming Interviews and those interviews have a threshold of about 45 minutes, and you have to come-up with an approach, wr
Most of us here are preparing for programming Interviews and those interviews have a threshold of about 45 minutes, and you have to come-up with an approach, write code, and explain. If you spend some time on the discuss section, you will realize there are some awesome solutions, which take you more than an interview-time to understand, let alone to come-up and code it. You may probably not hit the cool greedy solution, or the most optimized DP within time (though with time you will improve) but you should first practice to be able to solve the problem **within time**.\nIt is often helpful to keep a timer of 45 minutes to solve these problems, even if you are not able to solve it you will get enough understanding to explain your approaches and why those won\'t work out? Then move to discuss sections and try to understand a solution in 10-20 minutes. If you are able to understand in this time, you can code in the remaining time.\n\nSo, the following is what I came up within ~45 minutes:\nThis problem clearly speaks for a Dynamic Programmic approach. \nYou can imagine a state graph, \n* last state can have any values between [0, n]\n* if the last step was \'D\', the previous state can have only a higher value than what at the last state. Similarly, a lower value if step was \'I\'.\n* and the combination should be unique.\n\nThe third point, required some book-keeping of what numbers have appeared already. And I started out with a solution to keep the mask (as a tuple) (which as you may already know, won\'t work). After much brainstorming, I realized that it is not required to keep the details of which numbers (specifically) have appeared. It would just suffice to keep the details of the number of numbers haven\'t appeared and how many of them are lower (or higher) than the last number.\n\n```python\nclass Solution:\n    def numPermsDISequence(self, S: str) -> int:\n        N = len(S)\n        MOD = 10**9 + 7\n        \n        @lru_cache(None)\n        def dp(i, less, more):\n            res = 0\n            if(i < 0): return 1\n            if(less + more == 0): return 0\n            if(S[i] == \'I\'):\n                for k in range(less):\n                    res = (res + dp(i-1, k, less - k -1 + more)) % MOD\n            elif(S[i] == \'D\'):\n                for k in range(more):\n                    res = (res + dp(i-1, less + k, more - k - 1)) % MOD\n            return res\n        \n        return sum(dp(N-1, k, N-k) for k in range(N+1)) % MOD\n```
[]