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]
**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];
}
