当前位置 博文首页 > Grey Zeng：LeetCode 629. K Inverse Pairs Array
题目链接
定义dp[i][j]表示：1.....i范围内，形成j个逆序对有多少种方式，那么i和j的范围分别是：
i: [1...n]
j: [0...k]
其中我们把dp[0][...]位置弃而不用，因为没有意义，我们需要填好dp这个二维数组，并且返回dp[n][k]的值
dp[n][k]: 1...n范围内，生成k个逆序对有多少种方式，正好是题意要求。
由此可知，第0列的值是1，因为第0列表示1...i范围内，形成0个逆序对的数组有多少，只有一个（就是按顺序排列的那个）
int[][] dp = new int[n + 1][k + 1];
for (int i = 1; i <= n; i++) {
// 1....i范围内，形成0个逆序对的数组只有一个(按顺序排列那个）
dp[i][0] = 1;
}
对于普遍位置，按照i依次从i位置放到1位置，一共可以生成多少逆序对来做
比如：
通过7放在哪个位置来确定，此时要分两种情况
情况1：
dp[7][3]
7放倒数第一，dp[7][3] = dp[6][3] // 7放倒数第一，所以1..7产生的逆序对和1...6产生的逆序对一样，以下同理
7放倒数第二，dp[7][3] = dp[6][2]
7放倒数第三，dp[7][3] = dp[6][1]
7放倒数第四，dp[7][3] = dp[6][0]
情况2：
dp[7][7]
7放倒数第一，dp[7][7] = dp[6][7]
7放倒数第二，dp[7][7] = dp[6][6]
7放倒数第三，dp[7][7] = dp[6][5]
7放倒数第四，dp[7][7] = dp[6][4]
7放倒数第五，dp[7][7] = dp[6][3]
7放倒数第六，dp[7][7] = dp[6][2]
7放倒数第七，dp[7][7] = dp[6][1]
所以：
// dp[i][j] 普遍位置
// 按照i依次从i位置放到1位置，一共可以生成多少逆序对来做
for (int i = 2; i <= n; i++) {
for (int j = 1; j <= k; j++) {
// 通过7放在哪个位置来确定
// 情况1：dp[7][3]
// 7放倒数第一，dp[7][3] = dp[6][3]
// 7放倒数第二，dp[7][3] = dp[6][2]
// 7放倒数第三，dp[7][3] = dp[6][1]
// 7放倒数第四，dp[7][3] = dp[6][0]
// 情况2：dp[7][7]
// 7放倒数第一，dp[7][7] = dp[6][7]
// 7放倒数第二，dp[7][7] = dp[6][6]
// 7放倒数第三，dp[7][7] = dp[6][5]
// 7放倒数第四，dp[7][7] = dp[6][4]
// 7放倒数第五，dp[7][7] = dp[6][3]
// 7放倒数第六，dp[7][7] = dp[6][2]
// 7放倒数第七，dp[7][7] = dp[6][1]
for (int l = j; l >= Math.max(0, j - i + 1); l--) {
dp[i][j] += dp[i - 1][l];
dp[i][j] %= MOD;
}
}
}
完整代码如下，但是这个方法会超时，
public static int kInversePairs(int n, int k) {
// dp[i][j] : 1 ...i 范围内，形成j个逆序对有多少种方式
// dp[0][...] 弃而不用，因为没有意义
int[][] dp = new int[n + 1][k + 1];
for (int i = 1; i <= n; i++) {
// 1....i范围内，形成0个逆序对的数组只有一个(按顺序排列那个）
dp[i][0] = 1;
}
// dp[i][j] 普遍位置
// 按照i依次从i位置放到1位置，一共可以生成多少逆序对来做
for (int i = 2; i <= n; i++) {
for (int j = 1; j <= k; j++) {
// 通过7放在哪个位置来确定
// 情况1：dp[7][3]
// 7放倒数第一，dp[7][3] = dp[6][3]
// 7放倒数第二，dp[7][3] = dp[6][2]
// 7放倒数第三，dp[7][3] = dp[6][1]
// 7放倒数第四，dp[7][3] = dp[6][0]
// 情况2：dp[7][7]
// 7放倒数第一，dp[7][7] = dp[6][7]
// 7放倒数第二，dp[7][7] = dp[6][6]
// 7放倒数第三，dp[7][7] = dp[6][5]
// 7放倒数第四，dp[7][7] = dp[6][4]
// 7放倒数第五，dp[7][7] = dp[6][3]
// 7放倒数第六，dp[7][7] = dp[6][2]
// 7放倒数第七，dp[7][7] = dp[6][1]
for (int l = j; l >= Math.max(0, j - i + 1); l--) {
dp[i][j] += dp[i - 1][l];
dp[i][j] %= MOD;
}
}
}
return dp[n][k];
}
优化部分在于如下这个循环
for (int l = j; l >= Math.max(0, j - i + 1); l--) {
dp[i][j] += dp[i - 1][l];
dp[i][j] %= MOD;
}
我们还是以例子说明：
情况1：
dp[7][3]
7放倒数第一，dp[7][3] = dp[6][3]
7放倒数第二，dp[7][3] = dp[6][2]
7放倒数第三，dp[7][3] = dp[6][1]
7放倒数第四，dp[7][3] = dp[6][0]
dp[7][4]
7放倒数第一，dp[7][4] = dp[6][4]
7放倒数第二，dp[7][4] = dp[6][3]
7放倒数第三，dp[7][4] = dp[6][2]
7放倒数第四，dp[7][4] = dp[6][1]
7放倒数第五，dp[7][4] = dp[6][0]
所以 情况1：
dp[i][j] = dp[i][j-1] + dp[i-1][j]
对于情况2(j>=i 下发生)：
dp[7][9]
7放倒数第一，dp[7][9] = dp[6][9]
7放倒数第二，dp[7][9] = dp[6][8]
7放倒数第三，dp[7][9] = dp[6][7]
7放倒数第四，dp[7][9] = dp[6][6]
7放倒数第五，dp[7][9] = dp[6][5]
7放倒数第六，dp[7][9] = dp[6][4]
7放倒数第七，dp[7][9] = dp[6][3]
dp[7][8]
7放倒数第一，dp[7][8] = dp[6][8]
7放倒数第二，dp[7][8] = dp[6][7]
7放倒数第三，dp[7][8] = dp[6][6]
7放倒数第四，dp[7][8] = dp[6][5]
7放倒数第五，dp[7][8] = dp[6][4]
7放倒数第六，dp[7][8] = dp[6][3]
7放倒数第七，dp[7][8] = dp[6][2]
**dp[i][j] =dp[i][j] - dp[i - 1][j - i] **
**
优化版本的代码如下：
// 优化版本
public static int kInversePairs(int n, int k) {
// dp[i][j] : 1 ...i 范围内，形成j个逆序对有多少种方式
// dp[0][...] 弃而不用，因为没有意义
int[][] dp = new int[n + 1][k + 1];
for (int i = 1; i <= n; i++) {
// 1....i范围内，形成0个逆序对的数组只有一个(按顺序排列那个）
dp[i][0] = 1;
}
// dp[i][j] 普遍位置
// 按照i依次从i位置放到1位置，一共可以生成多少逆序对来做
for (int i = 2; i <= n; i++) {
for (int j = 1; j <= k; j++) {
// 优化
// 情况1：
// dp[7][3]
// 7放倒数第一，dp[7][3] = dp[6][3]
// 7放倒数第二，dp[7][3] = dp[6][2]
// 7放倒数第三，dp[7][3] = dp[6][1]
// 7放倒数第四，dp[7][3] = dp[6][0]
// dp[7][4]
// 7放倒数第一，dp[7][4] = dp[6][4]
// 7放倒数第二，dp[7][4] = dp[6][3]
// 7放倒数第三，dp[7][4] = dp[6][2]
// 7放倒数第四，dp[7][4] = dp[6][1]
// 7放倒数第五，dp[7][4] = dp[6][0]
// 所以 情况1： dp[i][j] = dp[i][j-1] + dp[i-1][j]
// 情况2：dp[7][9]
// 7放倒数第一，dp[7][9] = dp[6][9]
// 7放倒数第二，dp[7][9] = dp[6][8]
// 7放倒数第三，dp[7][9] = dp[6][7]
// 7放倒数第四，dp[7][9] = dp[6][6]
// 7放倒数第五，dp[7][9] = dp[6][5]
// 7放倒数第六，dp[7][9] = dp[6][4]
// 7放倒数第七，dp[7][9] = dp[6][3]
// dp[7][8]
// 7放倒数第一，dp[7][8] = dp[6][8]
// 7放倒数第二，dp[7][8] = dp[6][7]
// 7放倒数第三，dp[7][8] = dp[6][6]
// 7放倒数第四，dp[7][8] = dp[6][5]
// 7放倒数第五，dp[7][8] = dp[6][4]
// 7放倒数第六，dp[7][8] = dp[6][3]
// 7放倒数第七，dp[7][8] = dp[6][2]
// 情况2 ： j>=i 下发生
dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % MOD;
if (j >= i) {
dp[i][j] = (dp[i][j] - dp[i - 1][j - i] + MOD) % MOD;
}
}
}
return dp[n][k];
}
算法和数据结构笔记
