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

更多

算法和数据结构笔记

参考资料