LeetCode 629. K Inverse Pairs Array

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]