How to define the DP states (with clear picture explanation)
When I tried to understand lee215\'s solution, I got stuck. Then I redescribe this process to better understand the whole process. Credits go to lee215.  \nThe 
When I tried to understand lee215\'s [solution](https://leetcode.com/problems/valid-permutations-for-di-sequence/discuss/168278/C++JavaPython-DP-Solution-O(N2)), I got stuck. Then I redescribe this process to better understand the whole process. Credits go to lee215.  \nThe intuition is: given a string s, results of the number of permutations for the following strings are the same.\n```\n0,1,2\n1,2,3\n1,2,4\n```\n\nBased on this observation, we can use the index of the sorted unused digits to aggregate the results.\nI am going to improve the illustration and also state definition.\nDefine the state of DP[i][j] as:\n- i is the digit index.\n- j is the **index** of current digit from sorted(current digit + remaining digits).\n\nThe reason we define j in this way is:\nAll the following will have the same results based on the same string S.\n```\n0, 1,2\n1,2,3\n1,2,4\n```\nWe can use index to have an unified representation.\n```\n0, 1, 2   ->   0, 1,  2\n1, 2, 3   ->   0, 1,  2\n1, 2, 4   ->   0, 1,  2\n```\nAfter figuring out this, the transitions can be shown as below:![image](https://assets.leetcode.com/users/images/d146760c-7121-409f-be5d-a7d406029ae0_1623956092.467306.png)\n\n\nMore detail can be found [Here.](https://medium.com/@jim.morris.shen/hard-dp-77774c6a4695?source=friends_link&sk=d901fef6067a08fdbb184acfdeb8cf5e)\n\nAfter figuring out the state transitions, then the code is pretty simple.\nif "D": postfix sum\nif \'I\': prefix sum\n```\n/*\njimmy shen\nTime complexity: O(n^2)\nSpace complexity: O(n)\n*/\n\nint MOD = 1e9+7;\nclass Solution {\npublic:\n    int numPermsDISequence(string S) {\n        int N = S.size();\n        vector<int> dp(N+1, 1);\n        for (int i=1;i<N+1;++i){\n            int M = (N+1)-i;\n            vector<int> new_dp(M, 0);\n            if (S[i-1]==\'D\'){\n                //postfix sum\n                for (int j=dp.size()-2;j>=0;--j){\n                    dp[j] += dp[j+1]; \n                    if (dp[j]>=MOD)dp[j] %= MOD;\n                }\n                for (int j=0;j<M;++j){\n                    new_dp[j] = dp[j+1];\n                }\n            }\n            else{\n                //prefix sum\n                for (int j=1;j<dp.size();++j){\n                    dp[j] += dp[j-1]; \n                    if (dp[j]>=MOD)dp[j] %= MOD;\n                }\n                for (int j=0;j<M;++j){\n                    new_dp[j] = dp[j];\n                }\n            }\n            dp = new_dp;\n        }\n        int ret = 0;\n        for (int i=0;i<dp.size();++i){\n            ret+=dp[i];\n            if (ret>=MOD)ret %= MOD;}\n        return ret;\n    }\n};\n```
[]