被裁员被退婚，也是被我摊上了～
程序员老鬼约 5 分钟刚看到个贴子，姑娘年底被裁员不说，还赶上订婚告吹，理由竟然是——她婚前自己买了套房。
网友回帖里有说男方小气的，也有说姑娘“多虑”的，但我看了看，核心矛盾很简单：她想给自己留点安全感，男方却觉得这是“不信任”。
这不是沟通问题，这是三观不匹配的问题。婚前买房在现代人眼里就像给手机贴个膜，图个踏实，又不是为了防谁。
很多网友替姑娘惋惜，但我反而觉得，这是上天帮她提前避个雷。房子是她自己的，装修钱她也愿意拿，本来已经很有诚意了，还能被否定，那以后遇到事儿更难谈。
不过话说回来，30岁被催婚的压力确实烦，但为了不被催而将就，更亏。与其急着把自己塞进不合适的关系，不如等一个愿意跟你并肩、而不是控制你的人。【备注:文末可领最新资料】
面试题：K 个逆序对数组
题目叫「K 个逆序对数组」，一般完整说法是：
给你两个整数 n 和 k，问把数字 1 ~ n 排成一个数组，有多少种排列，它们里面刚好有 k 个逆序对。结果通常要对 1e9+7 取模。
逆序对是啥？ 很简单：下标 i < j，但 nums[i] > nums[j]，这一对 (i, j) 就算一个。
举个特别小的例子：n = 3，所有排列：
[1,2,3]：0 个逆序对 [1,3,2]：1 个（3,2） [2,1,3]：1 个（2,1） [2,3,1]：2 个（2,1）（3,1） [3,1,2]：2 个（3,1）（3,2） [3,2,1]：3 个
所以如果 k=2，答案就是 2 种。
暴力枚举全排列再数逆序对肯定不行，n 一大就炸了，这题标准解是动态规划 + 一点小优化。
怎么想到用 DP？
一个很自然的想法是： 我们不是一次性把 1..n 都排好，而是一个一个往里插。
先只看数字 1：
只有一种排法 [1]，逆序对数只能是0
再看数字 1,2：
在
[1]里插入2，可以插在：最后： [1,2]，新产生 0 个逆序对开头： [2,1]，新产生 1 个逆序对（2 > 1）
再看 1,2,3：
在每一个 2 个数的排列里，把 3插到不同的位置插到最右边不会新增逆序对，越往左插，新产生的逆序对就越多
于是有个很关键的观察：
当我们把数字
i放进前面已经排好的1..i-1里时， 最多会新产生i-1个逆序对（把它塞到最左边）。
这就非常适合 DP 去枚举「我今天多加了几个逆序对」。
状态怎么设计？
经典写法：
dp[i][j]表示： 用数字1..i能组成的、刚好有j个逆序对 的排列个数
考虑把第 i 个数插进来：
它可以插在最右边 → 新增 0 个逆序对 往左移动一格 → 新增 1 个 …… 最左边 → 新增 i-1个
也就是说： 如果我最后的逆序对总数是 j，那：
这一次我新增了 x个（x取值 0 ~min(j, i-1)）那之前 1..i-1必须有j - x个
翻译成公式就是：
dp[i][j] = dp[i-1][j]
+ dp[i-1][j-1]
+ ...
+ dp[i-1][j - (i-1)]
这样做有个问题： 如果你真的每次都把这一长串加一遍，时间复杂度会变成 O(n * k * n)，也就是 O(n^2 * k)，肯定会超时。
怎么办？用前缀和把这一坨加法变成 O(1)。
前缀和怎么优化？
注意上面的式子，其实就是「一段连续区间的和」。
我们可以这样写一个等价的形式（把区间滑动展开）：
dp[i][j] = sum_{x=0..min(j, i-1)} dp[i-1][j-x]
这玩意儿其实是 dp[i-1] 的一个「滑动窗口和」。 于是用前缀和数组 pre：
pre[j] = dp[i-1][0] + dp[i-1][1] + ... + dp[i-1][j]
那：
如果 j < i：dp[i][j] = pre[j]否则： dp[i][j] = pre[j] - pre[j-i]（把多出来的那段减掉）
再记得整个过程都要对 MOD = 1e9+7 取模， 减法后如果是负数补回去就行。
初始条件：
用 1 个数，只有一种数组
[1]，逆序对只能是 0dp[1][0] = 1一般也可以从
dp[0][0] = 1开始推，更统一。
最终答案：dp[n][k]。
时间复杂度：
外层 i = 1..n内层 j = 0..k每次 O(1) → 整体 O(n * k)，这就是这题能过的大致极限。
按上面的思路写个比较干净的 Java 版本：
classSolution{
privatestaticfinalint MOD = 1_000_000_007;
publicintkInversePairs(int n, int k){
// dp[i][j] 只跟 i-1 行有关，可以做成滚动数组
int[] dp = newint[k + 1];
int[] pre = newint[k + 1];
dp[0] = 1; // 用 1 个数（其实这里是 i=1 时的前一行 i=0）：只有 0 个逆序对
for (int i = 1; i <= n; i++) {
// 先根据上一行 dp 构建前缀和
pre[0] = dp[0];
for (int j = 1; j <= k; j++) {
pre[j] = pre[j - 1] + dp[j];
if (pre[j] >= MOD) pre[j] -= MOD;
}
// newDp 是当前这一行的 dp[i][*]
int[] newDp = newint[k + 1];
for (int j = 0; j <= k; j++) {
// 这一行的 j 不能比最大可能的逆序对还大
// 最大逆序对是 i * (i - 1) / 2
if (j > i * (i - 1) / 2) {
newDp[j] = 0;
continue;
}
// 取 dp[i-1][j] + ... + dp[i-1][j - (i-1)]
int left = j - (i - 1);
if (left <= 0) {
newDp[j] = pre[j];
} else {
newDp[j] = pre[j] - pre[left - 1];
if (newDp[j] < 0) newDp[j] += MOD;
}
}
dp = newDp;
}
return k < 0 ? 0 : dp[k];
}
}
上面这版注意了几件小事：
用滚动数组节省空间，只留一行 dp每层 i 再开一个 newDp，算完之后丢给 dp加减都要记得取模、处理负数 顺便剪枝： j > i*(i-1)/2的位置直接设为 0，省点计算
大概就这么回事儿，这题主要难在「想到插入第 i 个数会多出 0..i-1 个逆序对」，然后把那堆和用前缀和优化掉，一通顺下来就挺自然的。你要是愿意，还可以自己拿 n=3,4 小数据，把中间的 dp 表手算几行，对照一下更好理解。
-END-
我为大家打造了一份RPA教程，完全免费：songshuhezi.com/rpa.html