DP leetcode 903. Valid Permutations for DI Sequence

[C++/Java/Python] DP Solution O(N^2) - LeetCode Discuss

This problem is a DP problem which I got stuck for a long time.

look from large to small, as shown here

class Solution:
    def numPermsDISequence(self, S: str) -> int:
        dp = [1]*(len(S)+1)
        for s in S:
            if s=='D':
                dp = dp[:-1]
                for i in range(1, len(dp)):
                    dp[i] += dp[i-1]
            else:
                dp = dp[1:]
                for i in range(len(dp)-1)[::-1]:
                    dp[i]+=dp[i+1]
        return dp[0] % (10**9+7)

Look from small to large

class Solution:
    def numPermsDISequence(self, S: str) -> int:
        dp = [1]*(len(S)+1)
        for s in S:
            if s=='I':
                dp = dp[:-1]
                for i in range(1, len(dp)):
                    dp[i] += dp[i-1]
            else:
                dp = dp[1:]
                for i in range(len(dp)-1)[::-1]:
                    dp[i]+=dp[i+1]
        return dp[0] % (10**9+7)

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.
The intuition is that, given a string s, results of the number of permutations for
0,1,2
1,2,3
1,2,4
are the same.
Which means we can use the index of the sorted unused digits to aggregate the results.
I’d like to improve the illustration and also state definition.
I’d like to define the state of DP[i][j] as:
i is the digit index.
j is the index of the current digit from sorted(current digit + remaining digits).
The reason we define j in this way is
All the following will have the same results based on the same string S.
0, 1,2
1,2,3
1,2,4
We can use the index to have a unified representation.
After figuring out this, the transitions can be shown as below:

More detail can be found from my another Article