LC 100333. 统计逆序对的数目

https://leetcode.cn/problems/count-the-number-of-inversions/description/

感觉这题解法有点抽象，我看了题解大致知道是什么思路了。总之就是不要考虑每个位置的具体选择，是要考虑这些位置上数字的相对大小。

前面两个比较好理解，最后一个意思是：如果前面有i-1个选择的话，那么在i位置的选择，理论上可以增加0,1,..(i-1)个新逆序对。

感觉这个模型有点抽象，我感觉自己还不是完全地理解。但是如果认为这个模型是对的话，那么程序写起来不是很难。这题使用记忆化搜索效果会更好，因为许多逆序值可能不会出现。 

class Solution:
    def numberOfPermutations(self, n: int, requirements: List[List[int]]) -> int:
        MOD = 10 ** 9 + 7
        req = {x[0] + 1: x[1] for x in requirements}
        m = max([x[1] for x in requirements])
        dp = [[0] * (m + 1) for _ in range(n + 1)]
        dp[0][0] = 1

        for i in range(1, n + 1):
            for rev in range(m + 1):
                if i in req and rev != req[i]: continue
                res = 0
                for j in range(0, i):
                    # less than how many elements ? which is new rev.
                    if rev < j: break
                    res += dp[i - 1][rev - j]
                    # res %= MOD
                dp[i][rev] = res

        return dp[n][m] % MOD