Python O(N^3)/O(N^2) time O(N) space DP solution with clear explanation (no "relative rank" stuff)
Since I didn\'t understand the relative rank stuff, I found this problem to be quite confusing until I saw this thread:\nhttps://leetcode.com/problems/valid-per
Since I didn\'t understand the relative rank stuff, I found this problem to be quite confusing until I saw this thread:\nhttps://leetcode.com/problems/valid-permutations-for-di-sequence/discuss/169126/Visualization-Key-to-the-DP-solution:-imagine-cutting-a-piece-of-paper-and-separating-the-halves\n\n**Property: If we increment elements that are greater than or equal to a certain value the D or I property will not be broken, as this only makes "larger" elements even larger.**\n\nFrom this point, it is easier to see where the dynamic programming essence comes in. Basically the number of solutions with length i depends on, and can be derived from, the number of solutions with length i-1, as follows:\n\n    We increment all elements that are greater than or equal to 0, and see if we can append 0 to the end of the sequence.\n    We increment all elements that are greater than or equal to 1, and see if we can append 1 to the end of the sequence.\n    ...\n    We increment all elements that are greater than or equal to i, and see if we can append i to the end of the sequence.\n\n**Therefore, we only care about the last number of each existing valid permutation.**\n\nFor each j in the range (0, i), we want to find the number of valid permutations of len i ending in j. \n* When placing j following a decreasing instruction \'D\', we want the last number in the existing permutation to have a higher value. \n* When placing j following an increasing instruction \'I\', we want the last number in the existing permutation to have a lower value. \n\nWe use two DP arrays of len(S)+1, dp and dp2. We swap dp and dp2 at the end of each step.\n\n**D:** 10\nThe only valid permutation for \'D\' is 10.\n* solutions ending with 0: 1\n* solutions ending with 1: 0\n\n**DI:** 102, 201\nWe want the last number in each existing permutation to have a lower value than j.\n* \\# solutions ending with 0: 0\nWe cannot add a 0 to any existing valid permutation, since the only valid permutation for \'D\' is 10.\n* \\# solutions ending with 1: dp2[1] = dp[0], which is 1\nWe have 1 solution ending with a 0 we can add a 0 to, since we want the last number in the permutation to have a lower value.\n* \\# solutions ending with 2: dp2[2] = dp[0] + dp[1], which is 1\nWe have 1 solution ending with a 0 we can add a 2 to, since we want the last number in the permutation to have a lower value.\n\n**DID:** 5 permutations\nWe want the last number in each existing permutation to have a higher value than j. \n* \\# of solutions ending with 0: dp[0] + dp[1] + dp[2] = 2\nWe increment all elements in 102, 201 that are >= 0 to get 213 and 312, which we can add a 0 to.\n* \\# solutions ending with 1: dp[1] + dp[2] = 2\nWe increment all elements in 102, 201 that are >= 1 to get 203 and 302, which we can add a 1 to.\n* \\# solutions ending with 2: dp[2] = 1\nSimilarly, the permutation 102 becomes 103, which we can add a 2 to.\n* \\# solutions ending with 3: 0\n\n**DIDI:** 16 permutations\nFrom this point onward, only the number of permutations is listed for the sake of brevity.\n\nsolutions ending with 0: 0\nsolutions ending with 1: 2 (dp[0])\nsolutions ending with 2: 4 (dp[0] + dp[1])\nsolutions ending with 3: 5 (dp[0] + dp[1] + dp[2])\nsolutions ending with 4: 5 (dp[0] + dp[1] + dp[2] + dp[3])\n\nNow let\'s see the two different outcomes for adding an I or D to that sequence:\n\n**DIDID:** 61 permutations\nsolutions ending with 0: 16 (dp[0] + dp[1] + dp[2] + dp[3] + dp[4])\nsolutions ending with 1: 16 (dp[1] + dp[2] + dp[3] + dp[4])\nsolutions ending with 2: 14 (dp[2] + dp[3] + dp[4])\nsolutions ending with 3: 10 (dp[3] + dp[4])\nsolutions ending with 4: 5 (dp[4])\nsolutions ending with 5: 0\n\n**DIDII:** 35 permutations\nsolutions ending with 0: 0 \nsolutions ending with 1: 0 (dp[0])\nsolutions ending with 2: 2 (dp[0] + dp[1])\nsolutions ending with 3: 6 (dp[0] + dp[1] + dp[2])\nsolutions ending with 4: 11 (dp[0] + dp[1] + dp[2] + dp[3])\nsolutions ending with 5: 16 (dp[0] + dp[1] + dp[2] + dp[3] + dp[4])\n\nYou might be able to notice a pattern here:\nWhen placing j following a decreasing instruction \'D\', then dp2[j] = sum of dp[j] to dp[i-1]\nWhen placing j following an increasing instruction \'I\', then dp2[j] = sum of dp[0] to dp[j-1]\n\nTherefore:\n\n```\nclass Solution(object):\n    def numPermsDISequence(self, S):\n        """\n        :type S: str\n        :rtype: int\n        """\n        dp = [1 for c in range(len(S)+1)]\n        dp2 = [0 for c in range(len(S)+1)]\n        \n        for i in range(1, len(S) + 1):\n            if S[i-1] == \'D\':\n                for j in range(i+1):\n                    dp2[j] = sum(dp[j:i])\n            else:\n                for j in range(i+1):\n                    dp2[j] = sum(dp[:j])\n            dp, dp2 = dp2, dp\n            \n        return sum(dp) % 1000000007\n```\n\t\t\n\t\t\nThis solution is O(n^3)\nInstead of having to use sum() each inner loop, you can calculate prefix/suffix sums in order to bring the runtime down to O(n^2)
[]