标签: 动态规划
难度: Hard
对于一个整数数组 nums，逆序对是一对满足 0 <= i < j < nums.length 且 nums[i] > nums[j]的整数对 [i, j] 。
给你两个整数 n 和 k，找出所有包含从 1 到 n 的数字，且恰好拥有 k 个 逆序对 的不同的数组的个数。由于答案可能很大，只需要返回对 109 + 7 取余的结果。
示例 1：
输入：n = 3, k = 0 输出：1 解释： 只有数组 [1,2,3] 包含了从1到3的整数并且正好拥有 0 个逆序对。
示例 2：
输入：n = 3, k = 1 输出：2 解释： 数组 [1,3,2] 和 [2,1,3] 都有 1 个逆序对。
提示：
1 <= n <= 10000 <= k <= 1000运行时间: 196 ms
内存: 0.0 MB
class Solution:
def kInversePairs(self, n: int, k: int) -> int:
dp = [[0] * (k + 1) for _ in range(n + 1)]
dp[1][0] = 1
for i in range(2, n + 1):
cumulative = 0
for j in range(k + 1):
cumulative += dp[i - 1][j]
if j >= i:
cumulative -= dp[i - 1][j - i]
dp[i][j] = cumulative % (10**9+7)
return dp[n][k]
这个题解使用动态规划来解决问题。定义状态 dp[i][j] 表示使用从 1 到 i 的整数构成长度为 i 的排列，且恰好有 j 个逆序对的不同排列个数。状态转移方程为：dp[i][j] = dp[i-1][j] + dp[i-1][j-1] + ... + dp[i-1][j-i+1]，即在前 i-1 个数的排列中，再插入第 i 个数，可以产生 0 到 i-1 个新的逆序对。通过累加前 i-1 个数排列的逆序对个数来计算 dp[i][j]。最后返回 dp[n][k] 即为答案。
时间复杂度: O(n^2k)
空间复杂度: O(nk)
class Solution:
def kInversePairs(self, n: int, k: int) -> int:
# 定义 dp 数组，dp[i][j] 表示使用从 1 到 i 的整数构成长度为 i 的排列，且恰好有 j 个逆序对的不同排列个数
dp = [[0] * (k + 1) for _ in range(n + 1)]
# 初始化边界条件，长度为 1 的排列中逆序对个数只能为 0
dp[1][0] = 1
# 遍历所有的状态
for i in range(2, n + 1):
cumulative = 0
for j in range(k + 1):
# 累加 dp[i-1][j] 到 dp[i-1][j-i+1] 的值
cumulative += dp[i - 1][j]
if j >= i:
cumulative -= dp[i - 1][j - i]
dp[i][j] = cumulative % (10**9+7)
# 返回 dp[n][k] 作为答案
return dp[n][k]
在动态规划中，这种累加是为了计算所有可能的方式，在已有的排列中插入一个新的数字i而形成新的逆序对数目。具体地，考虑插入数字i到一个已有的排列中，这个数字可以插入在排列的任意位置，从最后一位（不增加逆序对）到第一位（增加i-1个逆序对）。因此，要计算恰好有j个逆序对的排列数，我们需要累加所有可能通过插入i到不同位置从而形成j个逆序对的排列数，这些就是`dp[i-1][j]`到`dp[i-1][j-i+1]`。
插入第i个数时可以选择插入到现有排列的不同位置，从第一个位置插入到最后一个位置。若插入到最后，则不产生新的逆序对（0个逆序对）。若插入到第一个位置，则所有i-1个已经存在的数都会与这个新插入的数形成逆序对（i-1个逆序对）。因此，插入位置的不同直接影响了新产生的逆序对的数量，范围从0到i-1。
在累加操作中，我们需要维护一个滑动窗口的和，这个和表示插入数字i到不同位置产生的新逆序对的数量。当`j >= i`时，意味着我们需要从总和中去掉那些不可能通过插入i来达到的逆序对数目，即`dp[i-1][j-i]`。这是因为当我们从i-1个元素的排列中取出任何超过j个逆序对的排列时，插入i无法达到恰好j个逆序对的目标。这样的操作确保了我们计数的精确性，维护了一个有效的窗口范围。
边界条件`dp[1][0] = 1`基于这样一个事实：当只有一个数字1时，只存在一种排列（即[1]），且这个排列中没有任何逆序对。因为只有一个元素，不可能与其他元素形成逆序对，因此逆序对的数量为0。这是初始化动态规划表时的基础情况，确保了从这一基础情况开始，可以正确计算出更大的n和k的情况。