线性动态规划：K个逆序对数组

题目描述

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

示例：
输入：n = 3, k = 1
输出：2
解释：数组 [1, 3, 2] 和 [2, 1, 3] 都有且仅有一个逆序对。

解题过程

这个问题要求我们统计所有特定排列的数量，直接枚举所有 n! 种排列是不现实的。我们需要找到排列的逆序对数量与排列构造过程之间的关系，并利用动态规划来高效地计数。

1. 定义状态
   我们定义 dp[i][j] 表示使用数字 1 到 i 能够构成的，恰好包含 j 个逆序对的不同数组的数量。
   我们的目标是求 dp[n][k]。

2. 寻找状态转移方程
   这是最关键的一步。我们思考如何从规模较小的问题（使用更少的数字）构建出当前规模的问题。

   • 基础： 当 i=1 时，只有一个数字 [1]，逆序对数为 0。所以 dp[1][0] = 1，对于 j>=1，dp[1][j] = 0。
   • 递推： 假设我们已经知道了所有使用数字 1 到 i-1 构成数组的情况（即 dp[i-1][*] 的值），现在我们要加入最大的数字 i。
     我们可以通过将数字 i 插入到一个由 (1, 2, ..., i-1) 构成的、已知逆序对数的数组中，来得到一个新的数组。
     这个由 i-1 个数构成的数组有 i 个位置可以插入新的数字 i（包括最前面和最后面，以及任意两个数字之间）。
     关键观察： 将数字 i 插入到某个位置，它会产生新的逆序对。具体来说，如果把它插入到该数组的末尾，由于 i 是最大的数，它不会与前面的任何数形成逆序对，新增逆序对数为 0。如果把它插入到倒数第二个位置，它会与它后面的那个数（原数组的最后一个数）形成一个逆序对，因为 i 大于那个数，新增逆序对数为 1。以此类推，如果把它插入到数组的最前面，那么它会与后面所有的 i-1 个数都形成逆序对，新增逆序对数为 i-1。
     • 插入位置 0（最前面）：新增 i-1 个逆序对。
     • 插入位置 1：新增 i-2 个逆序对。
     • ...
     • 插入位置 i-1（最后面）：新增 0 个逆序对。

   因此，对于一个已有的、逆序对数为 x 的数组（由 1 到 i-1 构成），通过插入数字 i，我们可以得到一个逆序对数为 x + new_pairs 的新数组，其中 new_pairs 可以是 0, 1, 2, ..., i-1。

   根据计数原理，要得到 dp[i][j]（即使用 1 到 i，逆序对数为 j 的数组数量），我们需要考虑所有可能的“前驱状态”。这个新数组的逆序对数 j，是由旧数组的逆序对数 prev_j 加上插入操作新增的逆序对数 new_pairs 构成的，即 j = prev_j + new_pairs。所以 prev_j = j - new_pairs。

   并且，对于每一个特定的旧数组（对应一个 dp[i-1][prev_j]），我们通过选择不同的插入位置（即不同的 new_pairs），可以产生多个新数组。但是，每一个旧数组，通过插入操作，都能产生 i 个不同的新数组（对应 new_pairs 从 0 到 i-1），并且这些新数组是互不相同的。

   所以，状态转移方程可以写成：
   dp[i][j] = Σ (dp[i-1][j - new_pairs])，其中 new_pairs 的取值范围是从 0 到 i-1。
   但是，j - new_pairs 必须是非负的，即 new_pairs <= j。同时，new_pairs 最大只能是 i-1。
   所以，new_pairs 的实际取值范围是 max(0, j - (i-1)) 到 j？不，让我们重新梳理一下。

   更准确地说，new_pairs 的取值是 0, 1, 2, ..., min(j, i-1)。因为新增的逆序对数不可能超过 i-1，也不可能比 j 还大（否则 prev_j 就成负数了）。
   所以，prev_j = j - new_pairs 的取值范围是从 j - min(j, i-1) 到 j。
   我们可以统一写成：
   dp[i][j] = Σ (dp[i-1][j - t])，其中 t 从 0 遍历到 min(j, i-1)。

   举例理解： 假设 i=3, j=2。

   • t 的取值范围是 0 到 min(2, 2) = 2。
   • 我们需要求和：dp[2][2-0] + dp[2][2-1] + dp[2][2-2] = dp[2][2] + dp[2][1] + dp[2][0]。
   • 这意味着，要构成一个由 {1,2,3} 组成的、有 2 个逆序对的数组，有三种方式：
     1. 从一个由 {1,2} 组成的、本身就有 2 个逆序对的数组（如 [2,1]）中，把 3 插在末尾（新增 0 个逆序对）。
     2. 从一个由 {1,2} 组成的、有 1 个逆序对的数组（如 [1,2] 的逆序对是0？不对，[1,2]逆序对是0。实际上，{1,2}能组成的数组只有[1,2]（0个逆序对）和[2,1]（1个逆序对）。所以 dp[2][1]=1, dp[2][2]=0。这里例子可能不完美，但说明了思想）中，把 3 插在中间（新增 1 个逆序对）。
     3. 从一个由 {1,2} 组成的、有 0 个逆序对的数组（如 [1,2]）中，把 3 插在最前面（新增 2 个逆序对）。

3. 初始化

   • dp[1][0] = 1，因为只有一个数字 [1]，逆序对为 0。
   • 对于任何 i，如果 j < 0，dp[i][j] = 0（逆序对数不能为负）。
   • 对于 i>=1，dp[i][0] = 1，因为严格递增的数组 [1,2,...,i] 逆序对为 0，并且只有这一种情况。

4. 计算顺序与优化
   如果我们直接使用上面的转移方程，需要三层循环：外层遍历 i 从 2 到 n，中层遍历 j 从 0 到 k，内层遍历 t 从 0 到 min(j, i-1)。时间复杂度是 O(n * k * min(n, k))，在 n 和 k 较大时（比如都达到1000）可能会超时。

   优化：利用前缀和
   观察转移方程：dp[i][j] = dp[i-1][j] + dp[i-1][j-1] + ... + dp[i-1][j - min(j, i-1)]。
   这实际上是在求 dp[i-1] 数组中，从下标 j - min(j, i-1) 到 j 的这个连续区间内的和。

   我们可以预先计算 dp[i-1] 数组的前缀和数组 prefix[i-1]，其中 prefix[i-1][x] = dp[i-1][0] + dp[i-1][1] + ... + dp[i-1][x]。
   那么，dp[i][j] = prefix[i-1][j] - prefix[i-1][j - min(j, i-1) - 1]。
   注意边界情况：当 j - min(j, i-1) - 1 < 0 时，我们设 prefix[i-1][-1] = 0。

   由于 min(j, i-1) = i-1 当 j >= i-1 时，否则为 j。
   我们可以更清晰地写成：

   • 如果 j < i： dp[i][j] = prefix[i-1][j] - 0 （因为 j - j - 1 < 0，后半部分为0）=prefix[i-1][j]。
   • 如果 j >= i： dp[i][j] = prefix[i-1][j] - prefix[i-1][j - i]。

   这样，对于每个 i 和 j，我们可以在 O(1) 时间内计算出 dp[i][j]。总时间复杂度优化为 O(n * k)。

5. 最终代码框架（伪代码）

   MOD = 10^9 + 7
   初始化一个二维数组 dp[n+1][k+1]，全部初始化为0。
   dp[1][0] = 1
   
   for i from 2 to n:
       // 计算上一行（i-1）的前缀和数组 prefix
       prefix[0] = dp[i-1][0]
       for j from 1 to k:
           prefix[j] = (prefix[j-1] + dp[i-1][j]) % MOD
   
       for j from 0 to k:
           if j < i:
               // 此时 min(j, i-1) = j
               // dp[i][j] = sum_{t=0 to j} dp[i-1][j-t] = sum_{x=0 to j} dp[i-1][x]
               dp[i][j] = prefix[j] // 因为 prefix[j] 就是 dp[i-1][0]到dp[i-1][j]的和
           else:
               // 此时 min(j, i-1) = i-1
               // dp[i][j] = sum_{t=0 to i-1} dp[i-1][j-t] = sum_{x=j-(i-1) to j} dp[i-1][x]
               dp[i][j] = (prefix[j] - prefix[j - i] + MOD) % MOD
               // 加上MOD再取模是为了防止负数
   
   return dp[n][k]
   

总结
这个问题的核心在于理解如何通过插入最大数来构建状态转移，并巧妙地利用前缀和优化来降低时间复杂度。它展示了动态规划在计数类问题中的强大能力，以及通过优化技巧处理大规模数据的方法。