Leetcode 3193. Count the Number of Inversions

• Leetcode 3193. Count the Number of Inversions
  • 1. 解题思路
  • 2. 代码实现

• 题目链接：3193. Count the Number of Inversions

1. 解题思路

这一题的话我的思路核心还是动态规划，因此核心就是迭代关系如何构建。

我们定义$f(n,k)$表示将1到$n$一共n个元素进行排列，一共有$k$个逆序pair的排列数目。我们考察$f(n+1,k)$的构造方式。

一种直接的构造就是基于$f(n,k)$，我们考虑如何加入元素$n+1$即可。如果将$n+1$放到最后一个元素，则必然有$k$个序列pair，如果要有$k+p$个逆序pair，那么我们基于$f(n,k)$当中的任意排列进行改造，只需要将元素$n-p$放置到最后一个元素，然后将所有原序列当中所有大于等于$n-p$的元素加1，就可以保持前$n$个元素依然保持$k$个逆序pair，而总的$n+1$个元素有$k+p$的逆序pair。

综上，我们即可整理得到迭代关系：

$$f(n+1,k)=\sum _{i=\max (0,k-n)}^{k}f(n,i)$$

我们将其翻译为代码语言并加入限制条件即可。

2. 代码实现

给出python代码实现如下：

MOD = 10**9+7class Solution:def numberOfPermutations(self, n: int, requirements: List[List[int]]) -> int:requirements = sorted(requirements)rq = {ed: cnt for ed, cnt in requirements}@lru_cache(None)def dp(idx, cnt):if idx == 0:return 1 if cnt == 0 else 0elif cnt > idx * (idx+1) // 2 or cnt < 0:return 0elif idx in rq and cnt != rq[idx]:return 0elif idx-1 in rq:return dp(idx-1, rq[idx-1]) if cnt-idx <= rq[idx-1] <= cnt else 0ans = 0for pre_cnt in range(cnt-idx, cnt+1):ans += dp(idx-1, pre_cnt)return ans % MODed, cnt = requirements[-1]ans = dp(ed, cnt)return ans

提交代码评测得到：耗时8757ms，占用内存116.3MB。