DeepSeek LeetCode 629.K个逆序对数组 public int kInversePairs(int n, int k)

这是LeetCode 629题“K个逆序对数组”的Java解法使用了动态规划与前缀和优化时间复杂度为O(nk)空间复杂度为O(nk)可优化至O(k)。publicclassSolution{publicintkInversePairs(intn,intk){finalintMOD1_000_000_007;// dp[i][j] 表示由 1..i 组成的排列中恰好包含 j 个逆序对的个数int[][]dpnewint[n1][k1];// 基础情况长度为0的排列有0个逆序对只有一种dp[0][0]1;for(inti1;in;i){dp[i][0]1;// 顺序排列逆序对为0for(intj1;jk;j){// 递推公式dp[i][j] dp[i-1][j] dp[i-1][j-1] ... dp[i-1][j-i1]// 利用前缀和优化为// dp[i][j] dp[i-1][j] dp[i][j-1] - (j i ? dp[i-1][j-i] : 0)longval(dp[i-1][j]dp[i][j-1])%MOD;if(ji){val(val-dp[i-1][j-i]MOD)%MOD;}dp[i][j](int)val;}}returndp[n][k];}}思路解释· 状态定义dp[i][j] 表示由数字 1…i 组成的排列中逆序对个数恰好为 j 的排列总数。· 转移方程考虑数字 i 插入到 i-1 的排列中。若放在最后不增加逆序对若放在倒数第 p 个位置则会增加 p-1 个逆序对因为它比后面 p-1 个数大。因此dp[i][j] \sum_{x0}^{\min(j, i-1)} dp[i-1][j-x]直接计算复杂度高使用前缀和优化dp[i][j] dp[i-1][j] dp[i][j-1] - (j \ge i ? dp[i-1][j-i] : 0)· 边界dp[0][0] 1dp[i][0] 1。· 模运算结果对 10^97 取模减法时需加 MOD 保证非负。复杂度分析· 时间复杂度O(nk)两层循环。· 空间复杂度O(nk)可进一步优化为 O(k) 的一维滚动数组需注意递推顺序。