Easy-to-understand solution with detailed explanation
\nBefore diving into the state transition function, let us first start with a simple example.\n\n### 1. a simple example\n\nIn the following discussion, for sim
\nBefore diving into the state transition function, let us first start with a simple example.\n\n### 1. a simple example\n\nIn the following discussion, for simplification, I will use both notation DI-seq and DI-rule instead of DI sequence.\n\nConsider a permutation 1032, which is based on a DI-seq "DID", how to use it to construct a new instance ending at **2** and based on DI-seq "DID**D**"?\n\n**Method**:\nstep 1.\nfor the original permutation `1032`, we add 1 to the digits *that are larger than or equal to* **2**.\n```C++\n1032->1043\n  ^^\n```\n\nstep 2.\nthen directly append **2**  to `1043`,  i.e., 1043 -> 1043**2**\n\n**Remark on step 1**:\n(1) By performing add operation, 2 in the original permutation now becomes 3, and thus there is no duplicate element for the new arrival **2**.\n(2) More importantly, such operation on the digits **will not break the original DI-rule**. e.g., 1043 still keeps its old DI-rule, i.e., "DID". The proof is straight-forward,  you can validate yourself.\n\nNow a new permutation with DI-rule "DID**D**" and ending at **2** has been constructed from 1032, namely 1043**2**.\n\n\nWith the same spirit, using 1032("DID"), we can construct instances with DI-rule "DID**D**": 2043**1**(ending with **1**), 2143**0**(ending with **0**).\n(Note that the instance(based on "DID**D**") which ends with 3 can not be constructed.)\n\n\n\nSimilarly, from 1032("DID"), we can construct instances with DI-rule "DID**I**": 10423(ending with **3**), 10324(ending with **4**).\n(Note that the instance(based on "DID**I**") which ends with 1 or 2 can not be constructed.)\n\n\n\n### 2. state transition function\n\nWith the example above in mind, the transition function seems to be clear.\n\nGiven a string DI-seq S, let `dp[i][j]` represents the number of permutation of number `0, 1, ... , i`, satisfying DI-rule S.substr(0, i), and ending with digit `j`.\n\n\n```C++\nif(S[i-1] == \'D\')\n   dp[i][j] = dp[i-1][j] + dp[i-1][j+1] + ... + dp[i-1][i-1]\n\nif(S[i-1] == \'I\') \n   dp[i][j] = dp[i-1][0] + dp[i-1][1] + ... + dp[i-1][j-1]\n```\n\n\n\n\n### 3.  Solution\n\n```C++\nlass Solution {\npublic:\n    int numPermsDISequence(string S) {\n        int n = S.size(), m = 1e9 + 7;\n        vector<vector<int>> dp(n+1, vector<int>(n+1, 0));\n        dp[0][0] = 1;\n        for(int i = 1; i <= n; i++)\n            for(int j = 0; j <= i; j++)\n                if(S[i-1] == \'D\')\n                    for(int k = j; k <= i-1; k++)\n                        dp[i][j] = dp[i][j]%m + dp[i-1][k]%m;\n                else\n                    for(int k = 0; k <= j-1; k++)\n                        dp[i][j] = dp[i][j]%m + dp[i-1][k]%m;\n        int res = 0;\n        for(int i = 0; i <= n; i++)\n            res = res%m + dp[n][i]%m;\n        return res%m;\n    }\n};\n```\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n
[]