LeetCode629.K个逆序对数组（dp）

LeetCode629.K个逆序数组（dp）

题目传送门

给出两个整数 n 和 k，找出所有包含从 1 到 n 的数字，且恰好拥有 k 个逆序对的不同的数组的个数。 逆序对的定义如下：对于数组的第i个和第 j个元素，如果满i < j且 a[i] > a[j]，则其为一个逆序对；否则不是。 由于答案可能很大，只需要返回 答案 mod 109 + 7 的值。

解析

本题主要参考的官方题解，但是官方题解有些地方当时理解的时候有些困难，在这里再记录一下，便于理解。 官方题解 f[i][j]表示长度为i的数组，恰好包含j个逆序对的方案数，第i个元素的所有可能取值为1~i中的一个数字，我们假设第i个元素为k，那么数组中逆序对的个数为一下两部分之和： 1.数字k与另外i-1个元素产生的逆序对的个数 2.另外i-1个元素内部产生的逆序对的个数

对第一部分：数字k放在最后一位，数组中有i-k个比数字k大的数，所以k贡献的逆序对个数为i-k 对第二部分：因为f[i][j]表示的有j个逆序对的情况，所以我们希望第二部分的逆序对个数为j-(i-k)，这里逆序对的个数只与元素的相对大小有关，不包含k的数组元素为1,…,k-1和k+1,…i。我们可以把后半部分整体减一，此时逆序对的个数不变，我们的目标变成了1,…i-1，希望它有j-(i-k)个逆序对，由此我们可以得到状态转移方程。 边界条件为： f[0][0]=1，不用任何数字构成一个空数组，包含0个逆序对 f[i][j= mod) dp[now][j] -= mod; else if (dp[now][j]