K个逆序对数组 题目描述 给定两个整数 n 和 k，我们需要找出所有包含从 1 到 n 的数字，且恰好拥有 k 个逆序对的不同的数组的数量。逆序对的定义如下：对于数组中的第 i 个和第 j 个元素，如果满足 i < j 且 a[ i] > a[ j ]，则其为一个逆序对。由于答案可能很大，结果需要对 10^9 + 7 取模。 例如，当 n=3, k=1 时，可能的数组有 [ 1, 3, 2]（逆序对：3>2），[ 2, 1, 3]（逆序对：2>1），[ 2, 3, 1]（逆序对：2>1, 3>1），[ 3, 1, 2]（逆序对：3>1, 3>2）。但其中只有 [ 1, 3, 2] 和 [ 2, 1, 3 ] 是恰好有1个逆序对的数组。所以答案是2。 解题过程 这个问题要求我们统计所有长度为n的排列中，逆序对数量恰好为k的排列个数。直接枚举所有排列对于较大的n和k是不可行的。我们需要使用动态规划来高效地计算这个数量。 第一步：定义状态 我们尝试寻找一个状态定义，能够描述问题的子结构。 考虑一个关键观察：当我们构建一个包含数字 1 到 n 的排列时，可以想象我们是按顺序（比如从1到n）将数字插入到一个空数组中。但一个更有效的方法是考虑排列的大小。 定义 dp[i][j] 为：由数字 1 到 i 组成的排列中，恰好包含 j 个逆序对的排列的个数。 我们的目标是求 dp[n][k] 。 第二步：寻找状态转移方程 现在我们思考如何从规模更小的问题推导出 dp[i][j] 。 假设我们已经知道所有由数字 1 到 i-1 组成的排列（即规模为 i-1）的逆序对情况。现在，我们想要生成一个由数字 1 到 i 组成的排列。我们可以通过在一个已有的、由 1 到 i-1 组成的排列中插入新的数字 i 来得到。 关键点在于：数字 i 是当前最大的数字。当我们把这个新数字 i 插入到一个长度为 i-1 的排列中时，插入的位置会影响新产生的逆序对的数量。 假设我们有一个由 1 到 i-1 组成的排列，它本身有 p 个逆序对。现在我们将数字 i 插入到这个排列的某个位置。考虑插入位置： 如果我们把 i 插入到排列的 最后 ，由于 i 是最大的，它不会与任何在它前面的数字形成逆序对（因为 i 比它们都大）。所以，新排列的逆序对数量仍然是 p 。 如果我们把 i 插入到排列的 倒数第二个 位置，那么它会与它后面的那个数字（原本在最后一个位置的数字）形成一个逆序对（因为 i 比它大）。所以，新排列的逆序对数量是 p + 1 。 如果我们把 i 插入到排列的 倒数第三个 位置，那么它会与它后面的两个数字各形成一个逆序对。所以，新排列的逆序对数量是 p + 2 。 ... 以此类推，如果我们把 i 插入到排列的 最前面 ，那么它会与它后面的所有 i-1 个数字都形成逆序对。所以，新排列的逆序对数量是 p + (i-1) 。 总结一下：当我们把数字 i 插入到一个已有的、长度为 i-1 的排列中时，插入的位置（从末尾开始数是第 0 个位置，倒数第1个位置，...，最前面是第 i-1 个位置）决定了新产生的逆序对数量。如果插入位置距离末尾有 x 个空隙（或者说，插入后数字 i 前面有 x 个数字），那么新产生的逆序对数量就是 x 。（因为 i 会比它后面的所有数字都大，从而与它们都形成逆序对）。 因此，对于一个原本有 p 个逆序对的排列，插入数字 i 后，新排列的逆序对数量 j 等于 p + x ，其中 x 是插入位置对应的新逆序对数量， x 的取值范围是 0 到 i-1。 为了得到恰好有 j 个逆序对的、长度为 i 的排列，我们需要考虑所有可能的、长度为 i-1 的排列，以及所有可能的插入位置。具体来说： dp[i][j] 的值，等于所有满足 p + x = j 的情况的求和。其中 p 是某个长度为 i-1 的排列的逆序对数， x 是插入新数字 i 时产生的新逆序对数。 更精确地，对于固定的 j ，我们需要考虑所有可能的 p 和 x ，使得 p + x = j 。其中 p 的取值范围是 dp[i-1] 中有效的逆序对数（即 p >=0 且 p <= max_inversions(i-1) ，长度为 i-1 的排列最多有 (i-1)*(i-2)/2 个逆序对），而 x 的取值范围是 0 到 i-1。 所以，状态转移方程可以写成： dp[i][j] = sum_{x=0}^{min(j, i-1)} dp[i-1][j-x] 这个公式的含义是：要形成长度为 i、逆序对为 j 的排列，我们可以从一个逆序对为 j-x 的长度为 i-1 的排列开始，然后将数字 i 插入到一个能产生恰好 x 个新逆序对的位置（即插入后数字 i 前面有 x 个数字）。 第三步：确定初始条件和边界 当排列长度为0或1时（i=0 或 i=1），如果要求逆序对 j=0，那么只有1种排列（空排列或 [ 1 ]）。如果 j>0，则为0。 我们可以定义 dp[0][0] = 1 。这表示空排列有0个逆序对，有1种情况（空排列本身）。 对于任何 i，如果 j < 0，那么 dp[i][j] = 0 ，因为逆序对数量不能为负数。 第四步：计算顺序和优化 我们可以使用两层循环来填充动态规划表。外层循环 i 从 1 到 n（排列的长度），内层循环 j 从 0 到 k（或者到当前 i 可能的最大逆序对数，但为了节省空间，我们可以只计算到 k，因为 j>k 的情况我们最终不需要）。 然而，直接使用上面的转移方程 dp[i][j] = sum_{x=0}^{min(j, i-1)} dp[i-1][j-x] 会导致时间复杂度为 O(n * k * i)，在最坏情况下是 O(n² * k)，当 n 和 k 较大时可能效率不高。 我们可以优化这个求和过程。注意到这个求和实际上是一个区间和： dp[i][j] 的值等于 dp[i-1][j] + dp[i-1][j-1] + ... + dp[i-1][j - min(j, i-1)] 。 更仔细地观察： dp[i][j] = sum_{x=0}^{min(j, i-1)} dp[i-1][j-x] = dp[i-1][j] + dp[i-1][j-1] + ... + dp[i-1][j - min(j, i-1)] 如果我们已经计算了 dp[i][j-1] ，那么： dp[i][j-1] = sum_{x=0}^{min(j-1, i-1)} dp[i-1][(j-1)-x] = dp[i-1][j-1] + dp[i-1][j-2] + ... + dp[i-1][j-1 - min(j-1, i-1)] 比较 dp[i][j] 和 dp[i][j-1] ： 当 j-1 >= i-1 时，即 j >= i 时， min(j, i-1) = i-1 , min(j-1, i-1)=i-1 。 dp[i][j] = dp[i-1][j] + dp[i-1][j-1] + ... + dp[i-1][j - (i-1)] dp[i][j-1] = dp[i-1][j-1] + dp[i-1][j-2] + ... + dp[i-1][(j-1) - (i-1)] = dp[i-1][j-1] + ... + dp[i-1][j-i] 所以， dp[i][j] = dp[i][j-1] + dp[i-1][j] - dp[i-1][j-i] （当 j >= i 时） 当 j < i 时， min(j, i-1) = j , min(j-1, i-1)=j-1 (如果 j>=1)。 dp[i][j] = dp[i-1][j] + dp[i-1][j-1] + ... + dp[i-1][0] dp[i][j-1] = dp[i-1][j-1] + ... + dp[i-1][0] （当 j>=1） 所以， dp[i][j] = dp[i][j-1] + dp[i-1][j] （当 j < i 时，且 j>=1）。当 j=0 时， dp[i][0] = dp[i-1][0] ，因为只能插在最后。 综合起来，我们可以得到优化的转移方程： dp[i][0] = 1 （对于任何 i，只有严格递增的排列有0个逆序对） 对于 j >= 1: 如果 j < i: dp[i][j] = dp[i][j-1] + dp[i-1][j] 如果 j >= i: dp[i][j] = dp[i][j-1] + dp[i-1][j] - dp[i-1][j-i] 注意，当 j-i < 0 时，我们视 dp[i-1][j-i] = 0 。 这样，每个状态 dp[i][j] 的计算时间就是 O(1)，总时间复杂度为 O(n * k)。 第五步：实现和取模 在代码实现中，我们需要注意减法操作后可能产生负数，所以在取模之前需要加上模数以确保结果非负。 我们使用一个二维数组 dp ，但注意到 dp[i] 只依赖于 dp[i-1] ，所以可以使用滚动数组优化空间到 O(k)。 最终答案 最终答案就是 dp[n][k] 。 让我们用 n=3, k=1 来验证一下： 初始化： dp[0][0]=1 i=1: 排列只有 [ 1 ]。逆序对只能为0。 dp[1][0] = 1 , dp[1][j>0]=0 。 i=2: 由1,2组成排列。 j=0: dp[2][0] 。根据规则 j=0 < i=2, 但 j=0 是特殊情况，直接为1？或者用公式：j=0，我们单独处理为1。或者从 j=0 开始递推： dp[2][0] = 1 (因为只有 [ 1,2 ])。 j=1: j=1 < i=2, 所以 dp[2][1] = dp[2][0] + dp[1][1] = 1 + 0 = 1 ? 但实际由1,2组成的排列中，逆序对为1的只有 [ 2,1] 这一个排列。所以 dp[2][1] 应该是1。正确。 i=3: 由1,2,3组成排列。 j=0: dp[3][0]=1 ([ 1,2,3 ]) j=1: j=1 < i=3, 所以 dp[3][1] = dp[3][0] + dp[2][1] = 1 + 1 = 2 。这和我们之前举例的 [ 1,3,2] 和 [ 2,1,3 ] 吻合。正确。 因此，这个动态规划方案是正确的。