K个逆序对数组 题目描述 给定两个整数 n 和 k，我们需要计算出所有由 1 到 n 的数字组成的、恰好包含 k 个逆序对的、不同的数组的数目。由于答案可能非常大，请将其对 10^9 + 7 取模后返回。 定义 ： 逆序对：在数组 arr 中，如果存在索引 i 和 j，满足 i < j 且 arr[ i] > arr[ j]，则 (arr[ i], arr[ j ]) 构成一个逆序对。 不同的数组指的是排列不同，例如 [ 1,2,3] 和 [ 1,3,2 ] 是不同的。 输入示例 ： n = 3, k = 1 输出 ： 2 解释 ： 由 1, 2, 3 组成的、恰好有 1 个逆序对的数组是 [ 1,3,2] 和 [ 2,1,3 ]。 解题过程 这个问题可以转化为：在构造 1 到 n 的排列时，如何控制其逆序对的数量。我们需要计算 恰好有 k 个逆序对 的排列数量。 第一步：核心思路 假设我们已经知道如何使用数字 1 到 n-1 构成的所有排列，现在加入数字 n。数字 n 是当前最大的数字。我们思考：将数字 n 插入到一个已有的、由 1 到 n-1 构成的排列中，会如何影响逆序对数量？ 关键观察 ： 在任意一个 1 到 n-1 的排列中，有 n 个位置可以插入数字 n（包括最前面和最后面）。 如果我们将 n 插入到位置 i（从 0 开始计数，表示插入后数字 n 前面有 i 个数字），由于 n 是最大的，它会和它前面的 i 个数字都形成逆序对吗？不，它会和它前面的 所有 i 个数字都形成逆序对吗？仔细想想：n 是最大的，所以它比前面所有数字都大。但逆序对的定义是 arr[ p] > arr[ q] 且 p < q。这里数字 n 是后来插入的，它的索引大于前面的数字，所以 n 和前面的数字不会构成逆序对（因为前面的数字索引小，但数值也小）。等等，我们需要重新梳理“插入位置”的含义。 实际上，更准确的理解方式是： 我们有一个已有的 1 到 n-1 的排列，它有特定的逆序对数量。 我们将数字 n 插入到这个排列的某个位置。假设我们将 n 插入到这个排列的 某个位置 ，这个位置是“在最终排列中，数字 n 之前有多少个数字”。我们称这个位置为 j（j 从 0 到 n-1）。 在最终排列中，数字 n 的前面有 j 个数字，后面有 (n-1-j) 个数字。 由于数字 n 是当前最大的，它和它前面的 j 个数字 不会 形成逆序对（因为前面的数字索引小，数值也小，是前 < 后，数值前小后大，不构成逆序条件）。但等一下，逆序对是“前大后小”。在最终排列中，数字 n 位于索引较大位置（如果我们从排列的末尾插入，则 n 可能在后面）。其实，我们需要看 n 相对于它后面的数字。 让我们采用正向构造思路： 我们从一个空排列开始，依次放入数字 1, 2, 3, ..., n。 当我们放入数字 i 时，它比之前放进去的所有数字都大。如果我们把 i 放在当前排列的 某个位置 ，这个位置决定了新增的逆序对数量。 正确的核心观点 ： 假设我们已经构建了 1 到 i-1 的某个排列，现在要加入数字 i。由于 i 是目前最大的数字，如果把它放在当前排列的 最后 ，那么它不会和前面的任何数字形成新的逆序对（因为前面的数字索引都小于它，但数值也小于它，不满足“前大后小”）。如果把它放在当前排列的 最前面 ，那么它前面没有数字，但它后面的所有数字（即之前的 1 到 i-1 的所有数字）的索引都大于它，而数值都小于它，这也不会形成逆序对吗？等等，我们来仔细定义一下“放在某个位置”。 更标准的动态规划状态定义是： 设 dp[i][j] 表示：使用数字 1 到 i 构成的所有排列中， 恰好有 j 个逆序对 的排列数量。 我们想求 dp[n][k] 。 状态转移 ： 已知 dp[i-1][*] ，我们想推出 dp[i][*] 。 考虑数字 i 应该插入到哪个位置。数字 i 是当前最大的，所以当我们将 i 插入到一个已有的 1 到 i-1 的排列中时，i 会跟在它后面（即索引比 i 大）的所有数字形成逆序对吗？不，如果我们把 i 插入到某个位置，比如位置 p（0 <= p <= i-1，表示插入后 i 前面有 p 个数字），那么 i 的索引是 p。在 i 后面有 (i-1-p) 个数字。这些数字的索引大于 p，但数值都小于 i。所以，i 和它后面的每一个数字都满足“索引小，数值大”，即 (i, 后面的某个数字) 构成一个逆序对。因为 i 索引小，数值大，后面的数字索引大，数值小，这满足逆序对条件（前大后小）。是的，这就对了。 所以 ：当把数字 i 插入到位置 p 时（位置是从 0 到 i-1，表示 i 前面有 p 个数字），会增加 (i-1-p) 个新的逆序对（因为这些后面的数字原本是 1 到 i-1 的排列，它们之间有旧的逆序对，但 i 的加入和它们形成新的逆序对）。 因此 ，如果我们有一个 1 到 i-1 的排列，它有 m 个逆序对。现在我们把 i 插入到位置 p，那么新的逆序对总数是： m + (i-1-p) 所以，如果我们想让最终逆序对总数为 j，那么我们需要 m = j - (i-1-p)。也就是说，从状态 dp[i-1][j - (i-1-p)] 转移到 dp[i][j] 。 由于 p 可以从 0 到 i-1，我们枚举所有可能的插入位置 p，然后累加： dp[i][j] = sum_{p=0 to i-1} dp[i-1][j - (i-1-p)] 前提是 j - (i-1-p) >= 0。 令 q = i-1-p，则 p 从 0 到 i-1 对应 q 从 i-1 到 0。所以上式变为： dp[i][j] = sum_{q=0 to i-1} dp[i-1][j - q] 其中 q 表示插入 i 时新增的逆序对数量，q 的范围是 0 到 i-1。 这个公式是核心 ： dp[i][j] = dp[i-1][j] + dp[i-1][j-1] + ... + dp[i-1][j-(i-1)] 其中，如果下标小于 0，则项为 0。 第二步：初始条件 当 i=0 时，没有数字，只有一种排列（空排列），并且逆序对数为 0。所以 dp[0][0] = 1 ，对于 j>0 有 dp[0][j] = 0 。 或者，从 i=1 开始考虑：只有一个数字 1，逆序对数为 0，所以 dp[1][0] = 1 ， dp[1][j>0] = 0 。 实际上，我们通常用 i 表示使用 1 到 i 的数字，i 从 0 到 n。dp[ 0][ 0 ] = 1 是基础。 第三步：直接动态规划 根据公式，我们可以写一个三重循环：外层 i 从 1 到 n，中层 j 从 0 到 k，内层 q 从 0 到 i-1 但不超过 j。复杂度是 O(n * k * n)，即 O(n² k)，在 n 和 k 较大时会超时（比如 n, k 都 1000 时，n² k 太大）。我们需要优化。 第四步：优化状态转移 注意 dp[i][j] 的公式是： dp[i][j] = sum_{q=0}^{min(i-1, j)} dp[i-1][j-q] 这相当于一个前缀和。 我们可以用另一个数组 prefix[i-1][j] = sum_{t=0}^{j} dp[i-1][t] 来快速计算。因为： dp[i][j] = prefix[i-1][j] - prefix[i-1][j-i] ？ 我们来验证一下。 sum_{q=0}^{min(i-1, j)} dp[i-1][j-q] 令 t = j - q，则当 q=0 时，t=j；当 q=i-1 时，t=j-(i-1)。 所以这个和等于 sum_{t=j-(i-1)}^{j} dp[i-1][t] ，其中 t 下限不小于 0。 这就是区间 [ j-(i-1), j ] 的和，可以用前缀和快速计算。 具体优化 ： 定义 prefix[i-1][x] = sum_{t=0}^{x} dp[i-1][t] （当 x <0 时，prefix=0）。 则 dp[i][j] = prefix[i-1][j] - (j-i >= 0 ? prefix[i-1][j-i] : 0) 。 这里 j-i 其实是 j - (i-1) - 1？我们检查一下： 区间是 [ j-(i-1), j] 的闭区间。和是 prefix[ i-1][ j] - prefix[ i-1][ j-i ]。因为： prefix[ i-1][ j] 是 [ 0, j ] 的和。 减去 prefix[ i-1][ j-i] 是减去 [ 0, j-i] 的和，剩下 [ j-i+1, j ] 的和。 我们希望的是 [ j-(i-1), j ] 的和，即左端点是 j-i+1。是的，匹配。 所以公式是： dp[i][j] = prefix[i-1][j] - (j-i >= 0 ? prefix[i-1][j-i] : 0) 这样，我们可以 O(1) 时间计算每个 dp[i][j] 。总复杂度 O(n* k)。 第五步：边界情况 当 j=0 时， dp[i][0] = 1 （因为只有严格递增的排列才有 0 个逆序对，而这种排列只有一种）。 当 i=0 且 j>0 时，dp[ 0][ j ] = 0。 注意前缀和数组可以实时更新，我们只需要一维数组 dp_prev[j] 和 prefix_prev[j] ，然后计算新的 dp_cur[j] 和 prefix_cur[j] 。 第六步：实现步骤 初始化 dp[0][0] = 1 ，但我们可以用一维数组 dp 表示上一行的值，大小是 k+1。 循环 i 从 1 到 n： 创建新数组 dp_new 长度为 k+1，初始化为 0。 计算 prefix_prev 为 dp 的前缀和数组（一维）。 对于每个 j 从 0 到 k： 计算 left = j - i, right = j。 sum = prefix_ prev[ right] - (left >= 0 ? prefix_ prev[ left ] : 0) 注意，当 left < 0 时，区间是 [ 0, j]，即 prefix_ prev[ j ]。 但根据公式，left = j-i。如果 left < 0，意味着 j-i < 0，即 j < i，此时区间是 [ 0, j]，和就是 prefix_ prev[ j ]。 所以： dp_new[j] = (prefix_prev[j] - (left >= 0 ? prefix_prev[left] : 0)) % MOD 更新 dp = dp_ new。 最终答案是 dp[k] （即 dp[ n][ k ]）。 注意：前缀和计算时，prefix_ prev[ x] 要能处理 x <0 的情况，我们可以在计算时用条件判断。 第七步：例子（n=3, k=1） 初始化：dp_ prev 表示 i=0 的情况，只有 dp_ prev[ 0 ] = 1，其他为 0。 i=1： dp_ new[ 0] = prefix_ prev[ 0] - (left=0-1=-1, 所以是 prefix_ prev[ 0 ] - 0) = 1 - 0 = 1 dp_ new[ 1] = prefix_ prev[ 1] - (left=1-1=0, 所以 prefix_ prev[ 1] - prefix_ prev[ 0 ]) = 1 - 1 = 0 所以 dp_ cur = [ 1,0]，即 dp[ 1 ] 的情况。 i=2： 计算 prefix_ prev = [ 1,1]（因为 dp_ prev=[ 1,0 ]） j=0: left=0-2=-2, dp_ new[ 0] = prefix_ prev[ 0 ] = 1 j=1: left=1-2=-1, dp_ new[ 1] = prefix_ prev[ 1 ] = 1 dp_ cur = [ 1,1 ] i=3： prefix_ prev = [ 1,2]（对 dp_ prev=[ 1,1] 求前缀和，注意长度是 k+1=2，即 prefix[ 0]=1, prefix[ 1 ]=1+1=2） j=0: left=0-3=-3, dp_ new[ 0] = prefix_ prev[ 0 ] = 1 j=1: left=1-3=-2, dp_ new[ 1] = prefix_ prev[ 1 ] = 2 dp_ cur = [ 1,2 ] 所以 dp[ 3][ 1 ] = 2，匹配示例。 最终算法复杂度 O(n* k)，空间复杂度 O(k)。