903. Valid Permutations for DI Sequence

今天这个题的解法，对以后做 DP 的题来说，很有记性意义。

class Solution(object):
    def numPermsDISequence(self, S):
        """
        :type S: str
        :rtype: int
        """
        n = len(S)
        table = [1] * (n + 1)
        for s in S:
            nt = len(table)
            if s == 'I':
                for i in range(1, nt):
                    table[i] += table[i - 1]
                table = table[:nt - 1]
            else:
                for i in range(nt - 1, 0, -1):
                    table[i - 1] += table[i]
                table = table[1:]

        res =  table[-1] if S[-1] == 'I' else table[0]
        return res % (10**9 + 7)

参考 https://leetcode.com/problems/valid-permutations-for-di-sequence/discuss/168278/C++JavaPython-DP-Solution-O(N2)

之后遇到下一个状态，比上一个状态有所改变的时候，就可以用这种时序的图例来分析一下。

dp[i][j] means the number of possible permutations of first i + 1 digits,
where the i + 1th digit is j + 1th smallest in the rest of digits.

dp[i][*] 表示第 i + 1 位数字进行排列是的符合条件的组合数。 dp[i][j] j 表示第 i + 1 次处理中，第 j + 1 小的数。