线性动态规划：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 ] 都有恰好一个逆序对。 解题过程 1. 问题分析 我们需要计算长度为 n 的排列（由 1 到 n 组成）中，恰好包含 k 个逆序对的排列数量。这是一个典型的计数类动态规划问题，关键在于找到状态定义和状态转移方程。 2. 动态规划状态定义 定义 dp[ i][ j] 表示使用数字 1 到 i 组成的排列中，恰好包含 j 个逆序对的排列数量。我们的目标是求 dp[ n][ k ]。 3. 状态转移思路 考虑如何从 dp[ i-1][ ] 推导出 dp[ i][ ]。当我们已经有一个由 1 到 i-1 组成的排列时，现在要插入数字 i（当前最大的数字）。这个数字 i 可以插入到排列的多个位置： 插入到最末尾：不会新增任何逆序对 插入到倒数第二个位置：新增 1 个逆序对（与原来的最后一个数字） 插入到倒数第三个位置：新增 2 个逆序对 ... 插入到最前面：新增 i-1 个逆序对 因此，当我们插入数字 i 时，根据插入位置的不同，可以新增 0 到 i-1 个逆序对。 4. 状态转移方程 根据上述分析，我们可以得到： dp[ i][ j] = dp[ i-1][ j] + dp[ i-1][ j-1] + dp[ i-1][ j-2] + ... + dp[ i-1][ j-(i-1) ] 其中，要求 j ≥ 0 且 j-(i-1) ≥ 0。对于超出范围的索引，其值视为 0。 5. 优化状态转移 直接计算上述求和会导致时间复杂度为 O(n²k)，当 n 和 k 较大时可能超时。我们可以使用前缀和优化： 定义前缀和数组 prefix[ i][ j] = dp[ i][ 0] + dp[ i][ 1] + ... + dp[ i][ j ] 那么状态转移可以简化为： dp[ i][ j] = prefix[ i-1][ j] - prefix[ i-1][ j-i ] （当 j ≥ i 时） dp[ i][ j] = prefix[ i-1][ j] （当 j < i 时） 这样每次状态转移可以在 O(1) 时间内完成。 6. 边界条件 dp[ 0][ 0 ] = 1（空排列有 0 个逆序对） 对于 i > 0，dp[ i][ 0 ] = 1（完全升序排列有 0 个逆序对） 对于 j < 0，dp[ i][ j ] = 0 7. 算法实现步骤 初始化 dp[ 0][ 0 ] = 1 对于 i 从 1 到 n： 计算前缀和数组 prefix[ i-1 ] 对于 j 从 0 到 k： 如果 j < i：dp[ i][ j] = prefix[ i-1][ j ] 否则：dp[ i][ j] = prefix[ i-1][ j] - prefix[ i-1][ j-i ] 返回 dp[ n][ k ] mod (10^9+7) 8. 复杂度分析 时间复杂度：O(nk) 空间复杂度：O(k)（可以使用滚动数组优化） 9. 示例验证 以 n=3, k=1 为例： i=1: dp[ 1][ 0]=1, dp[ 1][ 其他 ]=0 i=2: dp[ 2][ 0] = dp[ 1][ 0 ] = 1 dp[ 2][ 1] = dp[ 1][ 1] + dp[ 1][ 0 ] = 0 + 1 = 1 i=3: dp[ 3][ 0] = dp[ 2][ 0 ] = 1 dp[ 3][ 1] = dp[ 2][ 1] + dp[ 2][ 0 ] = 1 + 1 = 2 结果与题目示例一致。