线性动态规划：K个逆序对数组 题目描述 给定两个整数n和k，找出所有包含从1到n的数字，且恰好拥有k个逆序对的不同的数组的数量。逆序对的定义是：对于数组中的两个元素a[ i]和a[ j]，如果i < j且a[ i] > a[ j ]，则称这是一个逆序对。由于答案可能很大，只需要返回答案对10^9+7取模的结果。 解题过程 这个问题要求我们统计所有1到n的排列中，恰好包含k个逆序对的排列数量。我们需要使用动态规划来高效解决。 步骤1：理解问题本质 我们需要生成所有长度为n的排列（包含数字1到n各一次） 每个排列都有一定数量的逆序对 目标是统计恰好有k个逆序对的排列数量 步骤2：定义状态 定义dp[ i][ j ]表示使用数字1到i组成的排列中，恰好有j个逆序对的排列数量。 步骤3：寻找状态转移关系 考虑如何从dp[ i-1][ ]推导出dp[ i][ ]： 当我们已经有1到i-1的排列时，插入数字i 数字i是当前最大的数字，可以插入到排列的0到i-1位置 如果插入到位置p（从右往左数，0-indexed），会新增p个逆序对 状态转移方程： dp[ i][ j] = Σ(dp[ i-1][ j-p ])，其中p的范围是max(0, j-(i-1))到min(j, i-1) 步骤4：基础情况 dp[ 1][ 0] = 1（只有一个数字[ 1 ]，0个逆序对） dp[ 1][ j ] = 0（j > 0，不可能有逆序对） dp[ i][ 0 ] = 1（完全升序排列，0个逆序对） 步骤5：优化计算 直接计算上面的求和会导致O(n×k×min(n,k))的时间复杂度，可能超时。我们可以使用前缀和优化： 定义prefix[ i][ j] = Σ(dp[ i][ t ])，其中t从0到j 那么状态转移可以优化为： dp[ i][ j] = prefix[ i-1][ j] - prefix[ i-1][ j-i ]（当j≥i时） dp[ i][ j] = prefix[ i-1][ j ]（当j＜i时） 步骤6：算法实现 初始化dp[ 1][ 0 ] = 1 对于i从2到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 ] + MOD) % MOD 返回dp[ n][ k ] 步骤7：复杂度分析 时间复杂度：O(n×k) 空间复杂度：O(n×k)，可以优化到O(k)使用滚动数组 步骤9：示例验证 以n=3, k=2为例： 排列[ 1,2,3 ]：0个逆序对 排列[ 1,3,2 ]：1个逆序对(3,2) 排列[ 2,1,3 ]：1个逆序对(2,1) 排列[ 2,3,1 ]：2个逆序对(2,1)、(3,1) 排列[ 3,1,2 ]：2个逆序对(3,1)、(3,2) 排列[ 3,2,1 ]：3个逆序对(3,2)、(3,1)、(2,1) 恰好有2个逆序对的排列有2个：[ 2,3,1]和[ 3,1,2 ]，与算法结果一致。