2021-06-01：K个逆序对数组。给出两个整数 n 和 k，找出所有包含从 1 到 n 的数字，且恰好拥有 k 个逆序对的不

福大大架构师每日一题

发布于 2021-08-05 15:54:39

8420

发布于 2021-08-05 15:54:39

2021-06-01：K个逆序对数组。给出两个整数 n 和 k，找出所有包含从 1 到 n 的数字，且恰好拥有 k 个逆序对的不同的数组的个数。逆序对的定义如下：对于数组的第i个和第 j个元素，如果满i < j且 a[i] > a[j]，则其为一个逆序对；否则不是。由于答案可能很大，只需要返回答案 mod (10的9次方 + 7 )的值。

福大大答案2021-06-01：

动态规划。

代码用golang编写。代码如下：

package main

import "fmt"

func main() {
    n := 1000
    k := 1000
    ret1 := kInversePairs1(n, k)
    ret2 := kInversePairs2(n, k)
    fmt.Println(ret1, ret2)
}

func kInversePairs1(n int, k int) int {
    if n < 1 || k < 0 {
        return 0
    }
    dp := make([][]int, n+1)
    for i := 0; i < n+1; i++ {
        dp[i] = make([]int, k+1)
    }
    dp[0][0] = 1
    mod := 1000000007
    for i := 1; i <= n; i++ {
        dp[i][0] = 1
        for j := 1; j <= k; j++ {
            dp[i][j] = (dp[i][j-1] + dp[i-1][j]) % mod
            if j >= i {
                dp[i][j] = (dp[i][j] - dp[i-1][j-i] + mod) % mod
            }
        }
    }
    return dp[n][k]
}

func kInversePairs2(n int, k int) int {
    if n < 1 || k < 0 {
        return 0
    }
    mod := 1000000007
    dp := make([][]int, n+1)
    for i := 0; i < n+1; i++ {
        dp[i] = make([]int, k+1)
    }
    dp[0][0] = 1
    for i := 1; i <= n; i++ {
        dp[i][0] = 1
        for j := 1; j <= k; j++ {
            dp[i][j] = dp[i-1][j] + dp[i][j-1]
            if j >= i {
                dp[i][j] -= dp[i-1][j-i]
            }
            dp[i][j] %= mod
        }
    }
    if dp[n][k] < 0 {
        return dp[n][k] + mod
    }
    return dp[n][k]
}

执行结果如下：