2021-06-01：K个逆序对数组。给出两个整数 n 和 k，找出所有包含从 1 到 n 的数字，且恰好拥有 k 个逆序对的不同的数组的个数。逆序对的定义如下：对于数组的第i个和第 j个元素，如果满

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]

}

执行结果如下：

左神java代码

2021-06-01：K个逆序对数组。给出两个整数 n 和 k，找出所有包含从 1 到 n 的数字，且恰好拥有 k 个逆序对的不同的数组的个数。逆序对的定义如下：对于数组的第i个和第 j个元素，如果满的相关教程结束。