629.K个逆序对数组

链接：629.K个逆序对数组
难度：Hard
标签：动态规划
简介：给出两个整数 n 和 k，找出所有包含从 1 到 n 的数字，且恰好拥有 k 个逆序对的不同的数组的个数。

题解 1 - typescript

• 编辑时间：2021-11-11
• 执行用时：5508ms
• 内存消耗：45.3MB
• 编程语言：typescript
• 解法介绍：动态规划。

function kInversePairs(n: number, k: number): number {
  if (k === 0) return 1;
  const MOD = 10 ** 9 + 7;
  const dp: Map<number, number>[] = new Array(2).fill(0).map(_ => new Map());
  dp[0].set(0, 1);
  for (let i = 1; i < n; i++) {
    const map = dp[i % 2];
    map.clear();
    for (const [num, cnt] of dp[(i - 1) % 2].entries()) {
      for (let j = 0; j <= i; j++) {
        if (num + j > k) break;
        const cur = map.get(num + j) ?? 0;
        map.set(num + j, (cur + cnt) % MOD);
      }
    }
  }
  return dp[(n - 1) % 2].get(k) ?? 0;
}