LeetCode 629. K 个逆序对数组

Categories:

题目描述
思路分析
1. 解法一：前缀和优化 DP（推荐）
相似题目

题目描述

✅ 629. K 个逆序对数组

思路分析

解法一：前缀和优化 DP（推荐）

核心思路：

dp[i][j] 表示用 1..i 组成恰有 j 个逆序对的数组数量。

由 dp[i-1][j - t] 转移，t 表示新数插入位置。

使用前缀和将每一行的转移降为 O(1)。

复杂度分析：

时间复杂度：O(n * k)。

空间复杂度：O(k)，使用滚动数组。

class Solution {
    public int kInversePairs(int n, int k) {
        int mod = 1_000_000_007;
        int[] dp = new int[k + 1];
        dp[0] = 1;

        for (int i = 1; i <= n; i++) {
            int[] next = new int[k + 1];
            long sum = 0;
            for (int j = 0; j <= k; j++) {
                sum += dp[j];
                if (j >= i) {
                    sum -= dp[j - i];
                }
                sum = (sum % mod + mod) % mod;
                next[j] = (int) sum;
            }
            dp = next;
        }

        return dp[k];
    }
}

func kInversePairs(n int, k int) int {
	const mod = 1000000007
	dp := make([]int, k+1)
	dp[0] = 1

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

	return dp[k]
}

相似题目

题目	难度	考察点
315. 计算右侧小于当前元素的个数	困难	归并/树状数组
493. 翻转对	困难	归并/树状数组
673. 最长递增子序列的个数	中等	动态规划
377. 组合总和 Ⅳ	中等	动态规划
629. K 个逆序对数组	困难	动态规划

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/68134655