629.k个逆序对数组.md

629.k 个逆序对数组

/*
 * @lc app=leetcode.cn id=629 lang=typescript
 *
 * [629] K个逆序对数组
 */

// @lc code=start
function kInversePairs(n: number, k: number): number {}
// @lc code=end

解法 1: 动态规划

• 状态: dp[i][j] 表示第 i 个数,拥有 j 对逆序对
• 转移方程: dp[i][j]=sum(dp[i-1][max(j-i+1,0)]..dp[i-1][j-1])
• 边界: dp[i][0]=1

function kInversePairs(n: number, k: number): number {
  const MOD = 10 ** 9 + 7
  const dp: number[][] = new Array(n + 1).fill(0).map(() => new Array(k + 1).fill(0))
  for (let i = 1; i <= n; i++) {
    dp[i][0] = 1
    for (let j = 1; j <= k; j++) {
      let sum = 0
      for (let l = Math.max(j - i + 1, 0); l <= j; l++) {
        sum = (sum + dp[i - 1][l]) % MOD
      }
      if (sum === 0) break

      dp[i][j] = sum
    }
  }

  return dp[n][k]
}

优化时间: 使用前缀和来优化每次求 dp[i][j] 的时间

function kInversePairs(n: number, k: number): number {
  const MOD = 10 ** 9 + 7
  const dp: number[][] = new Array(n + 1).fill(0).map(() => new Array(k + 1).fill(0))
  for (let i = 1; i <= n; i++) {
    dp[i][0] = 1
    let sums = [0]
    for (let j = 1; j <= k; j++) {
      for (let l = sums.length; l <= j + 1; l++) {
        sums[l] = (sums[l - 1] + dp[i - 1][l - 1]) % MOD
      }

      dp[i][j] = (sums[j + 1] - sums[Math.max(j - i + 1, 0)] + MOD) % MOD
      if (dp[i][j] === 0) break
    }
  }

  return dp[n][k]
}

dp[i]本身已经存了和的信息,所以可以不用另外开一个数组来存和,直接利用dp[i]之前已经计算好的值

function kInversePairs(n: number, k: number): number {
  const MOD = 10 ** 9 + 7
  const dp: number[][] = new Array(n + 1).fill(0).map(() => new Array(k + 1).fill(0))
  dp[0][0] = 1
  for (let i = 1; i <= n; i++) {
    dp[i][0] = 1
    for (let j = 1; j <= k; j++) {
      dp[i][j] = (dp[i][j - 1] + dp[i - 1][j] - (dp[i - 1][j - i] ?? 0) + MOD) % MOD
      if (dp[i][j] === 0) break
    }
  }

  return dp[n][k]
}

优化空间: 每次只使用 i 和 i-1 的状态,可以只使用一个一维数组来保存状态

function kInversePairs(n: number, k: number): number {
  const MOD = 10 ** 9 + 7
  let cur = [1, ...new Array(k).fill(0)]
  for (let i = 1; i <= n; i++) {
    const next = [1, ...new Array(k).fill(0)]
    for (let j = 1; j <= k; j++) {
      next[j] = (next[j - 1] + cur[j] - (cur[j - i] ?? 0) + MOD) % MOD
      if (next[j] === 0) break
    }
    cur = next
  }

  return cur[k]
}

Case

test.each([
  { input: { n: 3, k: 0 }, output: 1 },
  { input: { n: 3, k: 1 }, output: 2 },
  { input: { n: 3, k: 3 }, output: 1 },
  { input: { n: 5, k: 5 }, output: 22 },
  { input: { n: 500, k: 500 }, output: 334048938 },
])('input: n = $input.n, k = $input.k', ({ input: { n, k }, output }) => {
  expect(kInversePairs(n, k)).toEqual(output)
})