教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载本文是「算法通关手册」项目AlgoNote中 0629. K 个逆序对数组 题解的深入扩展系统讲解一道难度为「困难」、标签为「动态规划」的计数类 DP 题目。文章将完整推导dp[i][j]状态定义与「插入数字 i」的状态转移过程重点剖析如何用**前缀和滑动窗口**把时间复杂度从 $O(n \times k \times i)$ 降到 $O(n \times k)$并给出可运行的 Python 参考代码与滚动数组空间优化方案。读完本文你不仅能独立解出本题还能掌握一类「状态转移是相邻窗口求和」的计数 DP 通用优化套路。1. 题目概述1.1 题目描述对于一个整数数组 $nums$逆序对是一对满足 $0 \le i j nums.length$ 且 $nums[i] nums[j]$ 的整数对 $[i, j]$。题目给定两个整数 $n$ 和 $k$要求找出所有包含从 $1$ 到 $n$ 的数字、且恰好拥有 $k$ 个「逆序对」的不同的数组的个数。由于答案可能很大只需要返回对 $10^9 7$ 取余的结果。1.2 数据范围$1 \le n \le 10^3$$0 \le k \le 10^3$$n$ 与 $k$ 均达到 $1000$ 量级这意味着 $O(n \times k)$ 级别约 $10^6$ 个状态的算法是可行的而更高阶的复杂度如 $O(n \times k \times i)$则会超时。1.3 示例示例 1输入n 3, k 0 输出1 解释 只有数组 [1,2,3] 包含了从 1 到 3 的整数并且正好拥有 0 个逆序对。示例 2输入n 3, k 1 输出2 解释 数组 [1,3,2] 和 [2,1,3] 都有 1 个逆序对。注意 $n 3$ 时数字 $1,2,3$ 共有 $3! 6$ 种排列其中逆序对数为 $0$ 的只有升序 $[1,2,3]$ 一种逆序对数为 $1$ 的有 $[1,3,2]$、$[2,1,3]$ 两种这也给出了后面 DP 结果的一个自查基准。2. 前置知识计数类 DP 与动态规划三要素本题求解的是「满足恰好 $k$ 个逆序对的排列数量」属于典型的计数问题。在「算法通关手册」的 计数类 DP 章节中定义计数类 DP一类使用动态规划方法来统计可行方案数目的问题。区别于求解最优解计数类 DP 需要统计所有满足条件的可行解数量同时需要满足不重复、不遗漏的条件。本题完全符合这一特征——我们只关心方案数目不关心具体排列长什么样。同时本题也满足 动态规划基础 章节中归纳的三大特征重叠子问题排列 $1 \sim i$ 中逆序对数为 $j$ 的方案数会被多个更大规模的子问题反复引用无后效性$dp[i][j]$ 一旦确定就不再改变只与更小规模的 $dp[i-1][\cdot]$ 有关与后续阶段无关计数类 DP 的经典求解路径就是「找到递归关系 → 列出递推式 → 用表格DP 数组递推求解」本文正是按照这条路径展开。3. 思路 1动态规划3.1 状态定义定义 $dp[i][j]$ 表示使用数字 $1$ 到 $i$ 组成的排列中恰好有 $j$ 个逆序对的排列数量。其中$i$ 的取值从 $0$ 到 $n$$i 0$ 表示空排列便于初始化$j$ 的取值从 $0$ 到 $k$。3.2 状态转移方程的推导插入法考虑如何从规模 $i - 1$ 的问题构造规模 $i$ 的问题在前 $i - 1$ 个数字的任意排列中把数字 $i$ 插入到任意位置。由于 $i$ 是当前最大的数字它和它前面的每一个数字都会构成一个逆序对。因此插入位置决定了新增逆序对的数量插入位置前方元素个数新增逆序对数插入到最后$0$$0$插入到倒数第二个$1$$1$………………插入到第一个$i - 1$$i - 1$即若在前 $i - 1$ 个数字的一个排列中插入了数字 $i$且该排列原有 $j - t$ 个逆序对则插入后总逆序对数为 $(j - t) t j$其中 $t$ 是插入新增的逆序对数取值范围为 $t 0, 1, \dots, \min(j, i - 1)$既不能超过 $j$也不能超过最多新增的 $i - 1$ 个。由于 $i - 1$ 个数字的每种排列对应 $i$ 个不同的插入位置且插入后得到的不同排列互不重复逆过程从排列中删除数字 $i$ 可唯一还原计数满足「不重复、不遗漏」。于是得到状态转移方程$$dp[i][j] \sum_{t0}^{\min(j,\ i-1)} dp[i-1][j-t]$$换元令 $u j - t$等价地写为$$dp[i][j] \sum_{u\max(0,\ j-i1)}^{j} dp[i-1][u]$$初始条件$dp[0][0] 1$$0$ 个数字、$0$ 个逆序对只有「空排列」这一种对于任意 $i$$dp[i][0] 1$$0$ 个逆序对只有一种排列即升序排列 $[1, 2, \dots, i]$其余 $dp[0][j] 0\ (j 0)$。最终结果为 $dp[n][k]$。3.3 朴素实现的复杂度问题若直接枚举 $t$ 求和转移代价为 $O(\min(j, i-1))$整体时间复杂度约为 $O(n \times k \times i)$在 $n, k \le 1000$ 的数据范围下会超时。因此必须优化求和过程。4. 前缀和优化滑动窗口4.1 把求和看成滑动窗口观察转移方程$$dp[i][j] \sum_{u\max(0,\ j-i1)}^{j} dp[i-1][u]$$固定 $i$ 时$dp[i][j]$ 本质上是上一行 $dp[i-1]$ 中以 $j$ 结尾、长度不超过 $i$ 的一段连续区间和。当 $j$ 逐 1 增加时这个窗口整体向右滑动一位——只需「加入新元素 $dp[i-1][j]$剔除窗口外的旧元素」即可完成一次转移无需重复求和。具体地将 $dp[i][j]$ 与 $dp[i][j-1]$ 做差$dp[i][j-1] \sum_{u\max(0,\ j-i)}^{j-1} dp[i-1][u]$当 $j i$ 时窗口下界始终为 $0$因此 $dp[i][j] dp[i][j-1] dp[i-1][j]$当 $j \ge i$ 时窗口下界上移需要额外减去被挤出窗口的 $dp[i-1][j-i]$。合并两种情况得到前缀和优化后的 O(1) 转移方程$$dp[i][j] dp[i][j-1] dp[i-1][j] - \begin{cases} dp[i-1][j-i], j \ge i \cr 0, j i \end{cases}$$4.2 正确性验证n 3, k 1以 $n 3, k 1$ 手动推演一遍验证方程与代码初始化$dp[0][0] 1$$i 1$$dp[1][0] 1$$dp[1][1] dp[1][0] dp[0][1] - dp[0][0] 1 0 - 1 0$$1$ 个数字最多 $0$ 个逆序对合理$i 2$$dp[2][0] 1$$dp[2][1] dp[2][0] dp[1][1] 1 0 1$$j 1 i 2$不减$dp[2][2] dp[2][1] dp[1][2] - dp[1][0] 1 0 - 1 0$$i 3$$dp[3][1] dp[3][0] dp[2][1] 1 1 2$。最终 $dp[3][1] 2$与题目示例 2 一致$dp[3][0] 1$与示例 1 一致。5. 参考代码5.1 二维 DP前缀和优化版以下为「算法通关手册」题解中给出的完整参考实现其中取模采用 Python 的%运算天然保证结果非负class Solution: def kInversePairs(self, n: int, k: int) - int: MOD 10**9 7 # dp[i][j] 表示使用 1 到 i 的数字恰好有 j 个逆序对的排列数 dp [[0] * (k 1) for _ in range(n 1)] # 初始化0 个数字0 个逆序对只有空排列一种 dp[0][0] 1 for i in range(1, n 1): dp[i][0] 1 # 0 个逆序对只有一种排列升序 for j in range(1, k 1): # 朴素转移dp[i][j] sum(dp[i-1][j-t])t ∈ [0, min(j, i-1)] # 前缀和优化窗口右移一位 加入 dp[i-1][j]剔除 dp[i-1][j-i]若 j i dp[i][j] (dp[i][j - 1] dp[i - 1][j]) % MOD # 减去超出窗口范围的部分j i 时dp[i-1][j-i] 被挤出窗口 if j i: dp[i][j] (dp[i][j] - dp[i - 1][j - i]) % MOD return dp[n][k]代码要点内层循环从 $j 1$ 递推到 $j k$保证计算 $dp[i][j]$ 时 $dp[i][j-1]$ 已就绪当 $j \ge i$ 时才减去 $dp[i-1][j-i]$这正是窗口长度达到上限 $i$一个排列中新增逆序对最多 $i - 1$ 个加上原有 1 个、共窗口长度 $i$后的边界处理$dp[i-1][j-i]$ 的下标满足 $0 \le j - i \le k$不会越界因为 $j \le k$且 $i \ge 1$。5.2 滚动数组空间优化到 O(k)从转移方程可以看出第 $i$ 行的计算只依赖第 $i - 1$ 行因此可以用两个一维数组交替滚动把空间复杂度从 $O(n \times k)$ 降到 $O(k)$class Solution: def kInversePairs(self, n: int, k: int) - int: MOD 10**9 7 # prev 表示 dp[i-1]cur 表示 dp[i]滚动交替使用 prev [0] * (k 1) prev[0] 1 # dp[0][0] 1 for i in range(1, n 1): cur [0] * (k 1) cur[0] 1 # dp[i][0] 1升序排列 for j in range(1, k 1): cur[j] (cur[j - 1] prev[j]) % MOD if j i: cur[j] (cur[j] - prev[j - i]) % MOD prev cur return prev[k]需要说明的是滚动数组方案必须保留完整上一行prev不能单数组原地正序覆盖因为 $j \ge i$ 时需要读取 $dp[i-1][j-i]$而该位置在正序原地更新中可能已被当前行覆盖。6. 复杂度分析以二维 DP 的优化实现为准时间复杂度$O(n \times k)$。外层遍历 $i \in [1, n]$内层遍历 $j \in [1, k]$每个状态仅做常数次加/减与取模运算需要填充 $n \times k$ 个动态规划状态。空间复杂度$O(n \times k)$使用二维数组存储动态规划状态采用滚动数组后可以优化到 $O(k)$。对比朴素枚举 $t$ 的 $O(n \times k \times i)$ 复杂度前缀和优化将每次转移的求和代价降为 $O(1)$是本题能否在 $n, k \le 10^3$ 限制内通过的关键。7. 小结与仓库导航本题是一道典型的计数类动态规划 前缀和优化题目核心收获有三点插入法构造状态转移用「把最大元素 $i$ 插入前 $i-1$ 个数字的排列」这一视角将新增逆序对数与插入位置一一对应从而写出递推式滑动窗口/前缀和优化当转移是对上一行某段连续区间求和且窗口随下标滑动时用 $dp[i][j] dp[i][j-1] dp[i-1][j] - dp[i-1][j-i]$ 把单次转移降为 $O(1)$滚动数组降维状态只依赖相邻上一行时可用两个一维数组把空间从 $O(n \times k)$ 压到 $O(k)$。在「算法通关手册」仓库中你可以沿着以下路径继续深入本题题解原文docs/solutions/0600-0699/k-inverse-pairs-array.md标签「动态规划」、难度「困难」题目总览docs/00_preface/00_05_solutions_list.md 中收录本题本章题解索引见 docs/solutions/0600-0699/index.md动态规划方法论从 动态规划基础 出发理解最优子结构、重叠子问题与无后效性再通过 计数类 DP 掌握「统计方案数」类题目的通用建模方式如「不同路径」「整数拆分」等经典例题分类题目清单可参考 docs/00_preface/00_06_categories_list.md。「滑动窗口求和 前缀和」的优化手法在计数 DP 中通用性强当转移方程呈现 $dp[i][j] \sum dp[i-1][\cdot]$ 的连续区间求和形式时都应优先考虑用前缀和把内层枚举压缩为 $O(1)$ 转移。赞分享教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载相关推荐AlgoNote 算法通关手册LeetCode 0560「和为 K 的子数组」前缀和 哈希表解法全解AlgoNote 算法通关手册LeetCode 0560「和为 K 的子数组」前缀和 哈希表解法全解 本文是 AlgoNote 算法通关手册中「数组、哈希教程文档知识库算法通关手册LeetCode 0120 三角形最小路径和的动态规划详解与滚动数组优化算法通关手册LeetCode 0120 三角形最小路径和的动态规划详解与滚动数组优化 本文是「算法通关手册AlgoNote」中 0120. 三角形最小路径教程文档知识库AlgoNote 算法通关手册LeetCode 0053 最大子数组和的动态规划与分治三解法精讲AlgoNote 算法通关手册LeetCode 0053 最大子数组和的动态规划与分治三解法精讲 导读 本文围绕「算法通关手册」AlgoNote 仓库中的经典教程文档知识库上一篇LunaTranslator 视觉小说翻译器边玩边读实时中文字幕10 分钟跑通下一篇3步解锁专业级音频修复VoiceFixer让你的声音瞬间清晰如新创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考