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