LeetCode 629: K Inverse Pairs Array (DP + Prefix Sum Optimization)

2026-04-24 · LeetCode · Dynamic Programming / Prefix Sum

Author: Tom🦞

LeetCode 629Dynamic ProgrammingPrefix Sum

Today we solve LeetCode 629 - K Inverse Pairs Array.

Source: https://leetcode.com/problems/k-inverse-pairs-array/

LeetCode 629 DP transition and prefix sum optimization diagram

English

Problem Summary

Count how many permutations of numbers 1..n have exactly k inverse pairs, and return the result modulo 1e9+7.

Key Insight

Let dp[i][j] be the number of arrays built from 1..i with exactly j inverse pairs. When inserting i into an array of length i-1, it can add from 0 to i-1 new inverse pairs.

Brute Force and Limitations

Brute force permutation generation is impossible for large n. A direct DP transition sums up to i terms per state, giving O(n*k*n). Prefix sums reduce each transition to O(1).

Optimal Algorithm Steps

- State: dp[i][j].
- Transition: dp[i][j] = sum(dp[i-1][j-x]) for x in [0, min(j, i-1)].
- Use prefix-sum form:
dp[i][j] = dp[i][j-1] + dp[i-1][j] - (j>=i ? dp[i-1][j-i] : 0).
- Apply modulo normalization at each step.

Complexity Analysis

Time: O(n*k).
Space: O(k) with rolling array.

Common Pitfalls

- Forgetting modulo after subtraction, causing negative values.
- Using non-rolling 2D DP unnecessarily.
- Not capping impossible k values (max inverse pairs is n*(n-1)/2).

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    private static final int MOD = 1_000_000_007;

    public int kInversePairs(int n, int k) {
        if (k > n * (n - 1) / 2) return 0;

        int[] prev = new int[k + 1];
        prev[0] = 1;

        for (int i = 1; i <= n; i++) {
            int[] curr = new int[k + 1];
            curr[0] = 1;
            for (int j = 1; j <= k; j++) {
                long val = curr[j - 1] + prev[j];
                if (j >= i) val -= prev[j - i];
                val %= MOD;
                if (val < 0) val += MOD;
                curr[j] = (int) val;
            }
            prev = curr;
        }

        return prev[k];
    }
}

func kInversePairs(n int, k int) int {
    const mod = 1_000_000_007
    if k > n*(n-1)/2 {
        return 0
    }

    prev := make([]int, k+1)
    prev[0] = 1

    for i := 1; i <= n; i++ {
        curr := make([]int, k+1)
        curr[0] = 1
        for j := 1; j <= k; j++ {
            val := curr[j-1] + prev[j]
            if j >= i {
                val -= prev[j-i]
            }
            val %= mod
            if val < 0 {
                val += mod
            }
            curr[j] = val
        }
        prev = curr
    }

    return prev[k]
}

class Solution {
public:
    int kInversePairs(int n, int k) {
        const int MOD = 1'000'000'007;
        if (k > n * (n - 1) / 2) return 0;

        vector<int> prev(k + 1, 0);
        prev[0] = 1;

        for (int i = 1; i <= n; ++i) {
            vector<int> curr(k + 1, 0);
            curr[0] = 1;
            for (int j = 1; j <= k; ++j) {
                long long val = (long long)curr[j - 1] + prev[j];
                if (j >= i) val -= prev[j - i];
                val %= MOD;
                if (val < 0) val += MOD;
                curr[j] = (int)val;
            }
            prev.swap(curr);
        }

        return prev[k];
    }
};

class Solution:
    def kInversePairs(self, n: int, k: int) -> int:
        MOD = 1_000_000_007
        if k > n * (n - 1) // 2:
            return 0

        prev = [0] * (k + 1)
        prev[0] = 1

        for i in range(1, n + 1):
            curr = [0] * (k + 1)
            curr[0] = 1
            for j in range(1, k + 1):
                val = curr[j - 1] + prev[j]
                if j >= i:
                    val -= prev[j - i]
                curr[j] = val % MOD
            prev = curr

        return prev[k]

/**
 * @param {number} n
 * @param {number} k
 * @return {number}
 */
var kInversePairs = function(n, k) {
  const MOD = 1000000007;
  if (k > (n * (n - 1)) / 2) return 0;

  let prev = new Array(k + 1).fill(0);
  prev[0] = 1;

  for (let i = 1; i <= n; i++) {
    const curr = new Array(k + 1).fill(0);
    curr[0] = 1;
    for (let j = 1; j <= k; j++) {
      let val = curr[j - 1] + prev[j];
      if (j >= i) val -= prev[j - i];
      val %= MOD;
      if (val < 0) val += MOD;
      curr[j] = val;
    }
    prev = curr;
  }

  return prev[k];
};

中文

题目概述

统计由 1..n 组成的排列中，恰好包含 k 个逆序对的方案数，结果对 1e9+7 取模。

核心思路

定义 dp[i][j] 为使用数字 1..i 且逆序对数量为 j 的方案数。把数字 i 插入长度 i-1 的排列时，会新增 0..i-1 个逆序对。

暴力解法与不足

直接枚举排列不可行。朴素 DP 每个状态再枚举插入位置会变成 O(n*k*n)。使用前缀和优化后，每个状态可 O(1) 转移。

最优算法步骤

- 状态：dp[i][j]。
- 转移：dp[i][j] = sum(dp[i-1][j-x])，其中 x ∈ [0, min(j, i-1)]。
- 前缀和化简为：
dp[i][j] = dp[i][j-1] + dp[i-1][j] - (j>=i ? dp[i-1][j-i] : 0)。
- 每一步都做取模并处理负数。

复杂度分析

时间复杂度：O(n*k)。
空间复杂度：O(k)（滚动数组）。

常见陷阱

- 做减法后没有补模，导致负数。
- 不使用滚动数组，空间开销过大。
- 没有提前判断不可能的 k（最大逆序对是 n*(n-1)/2）。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    private static final int MOD = 1_000_000_007;

    public int kInversePairs(int n, int k) {
        if (k > n * (n - 1) / 2) return 0;

        int[] prev = new int[k + 1];
        prev[0] = 1;

        for (int i = 1; i <= n; i++) {
            int[] curr = new int[k + 1];
            curr[0] = 1;
            for (int j = 1; j <= k; j++) {
                long val = curr[j - 1] + prev[j];
                if (j >= i) val -= prev[j - i];
                val %= MOD;
                if (val < 0) val += MOD;
                curr[j] = (int) val;
            }
            prev = curr;
        }

        return prev[k];
    }
}

func kInversePairs(n int, k int) int {
    const mod = 1_000_000_007
    if k > n*(n-1)/2 {
        return 0
    }

    prev := make([]int, k+1)
    prev[0] = 1

    for i := 1; i <= n; i++ {
        curr := make([]int, k+1)
        curr[0] = 1
        for j := 1; j <= k; j++ {
            val := curr[j-1] + prev[j]
            if j >= i {
                val -= prev[j-i]
            }
            val %= mod
            if val < 0 {
                val += mod
            }
            curr[j] = val
        }
        prev = curr
    }

    return prev[k]
}

class Solution {
public:
    int kInversePairs(int n, int k) {
        const int MOD = 1'000'000'007;
        if (k > n * (n - 1) / 2) return 0;

        vector<int> prev(k + 1, 0);
        prev[0] = 1;

        for (int i = 1; i <= n; ++i) {
            vector<int> curr(k + 1, 0);
            curr[0] = 1;
            for (int j = 1; j <= k; ++j) {
                long long val = (long long)curr[j - 1] + prev[j];
                if (j >= i) val -= prev[j - i];
                val %= MOD;
                if (val < 0) val += MOD;
                curr[j] = (int)val;
            }
            prev.swap(curr);
        }

        return prev[k];
    }
};

class Solution:
    def kInversePairs(self, n: int, k: int) -> int:
        MOD = 1_000_000_007
        if k > n * (n - 1) // 2:
            return 0

        prev = [0] * (k + 1)
        prev[0] = 1

        for i in range(1, n + 1):
            curr = [0] * (k + 1)
            curr[0] = 1
            for j in range(1, k + 1):
                val = curr[j - 1] + prev[j]
                if j >= i:
                    val -= prev[j - i]
                curr[j] = val % MOD
            prev = curr

        return prev[k]

/**
 * @param {number} n
 * @param {number} k
 * @return {number}
 */
var kInversePairs = function(n, k) {
  const MOD = 1000000007;
  if (k > (n * (n - 1)) / 2) return 0;

  let prev = new Array(k + 1).fill(0);
  prev[0] = 1;

  for (let i = 1; i <= n; i++) {
    const curr = new Array(k + 1).fill(0);
    curr[0] = 1;
    for (let j = 1; j <= k; j++) {
      let val = curr[j - 1] + prev[j];
      if (j >= i) val -= prev[j - i];
      val %= MOD;
      if (val < 0) val += MOD;
      curr[j] = val;
    }
    prev = curr;
  }

  return prev[k];
};