题目

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

逆序对的定义如下：对于数组的第i个和第 j个元素，如果满i < j且 a[i] > a[j]，则其为一个逆序对；否则不是。

由于答案可能很大，只需要返回 答案 mod 109 + 7 的值。

示例 1:输入: n = 3, k = 0输出: 1

解释: 只有数组 [1,2,3] 包含了从1到3的整数并且正好拥有 0 个逆序对。

示例 2:输入: n = 3, k = 1输出: 2

解释: 数组 [1,3,2] 和 [2,1,3] 都有 1 个逆序对。

说明: n 的范围是 [1, 1000] 并且 k 的范围是 [0, 1000]。

解题思路分析

1、动态规划；时间复杂度O(n^2)，空间复杂度O(n^2)

var mod = 1000000007

func kInversePairs(n int, k int) int {
   dp := make([][]int, n+1) // dp[n][k]表示1-n的排列中，包含k个逆序对
   for i := 0; i <= n; i++ {
      dp[i] = make([]int, k+1)
   }
   for i := 1; i <= n; i++ {
      dp[i][0] = 1
      // 最多i*(i-1)/2
      for j := 1; j <= k && j <= i*(i-1)/2; j++ {
         // 前面i-1个数，i个插入位
         // 插入到最后，不增加： f(i,j) = f(i,j) + f(i-1,j)
         // 插入到倒数第2个，增加：f(i,j) = f(i,j) + f(i-1,j-1)
         // ...
         // 插入到倒数第i个，增加：f(i,j) = f(i,j) + f(i-1,j-i+1)
         // => f(i,j) = f(i-1,j) + f(i-1,j-1) + ... + f(i-1,j-i+1)
         // f(i,j-1) = f(i-1, j-1)+ ...+f(i-1, j-i)
         // f(i,j) - f(i,j-1) = f(i-1,j)-f(i-1, j-i)
         // => f(i, j) = f(i,j-1)+f(i-1,j)-f(i-1,j-i)
         if j >= i {
            dp[i][j] = dp[i][j-1] + dp[i-1][j] - dp[i-1][j-i]
         } else {
            dp[i][j] = dp[i][j-1] + dp[i-1][j]
         }
         if dp[i][j] >= 0 {
            dp[i][j] = dp[i][j] % mod
         } else {
            dp[i][j] = (dp[i][j] + mod) % mod
         }
      }
   }
   return dp[n][k]
}

2、动态规划+前缀和；时间复杂度O(n^2)，空间复杂度O(n)

var mod = 1000000007

func kInversePairs(n int, k int) int {
   dp := make([]int, k+1) // dp[k]包含k个逆序对的方案数
   dp[0] = 1
   sum := make([]int, k+2)
   sum[1] = 1
   for i := 1; i <= n; i++ {
      // 最多i*(i-1)/2
      for j := 1; j <= k && j <= i*(i-1)/2; j++ {
         // 前面i-1个数，i个插入位
         // 插入到最后，不增加： f(i,j) = f(i,j) + f(i-1,j)
         // 插入到倒数第2个，增加：f(i,j) = f(i,j) + f(i-1,j-1)
         // ...
         // 插入到倒数第i个，增加：f(i,j) = f(i,j) + f(i-1,j-i+1)
         // => f(i,j) = f(i-1,j) + f(i-1,j-1) + ... + f(i-1,j-i+1)
         // => f(j) = sum[j+1] - sum[j-i+1]
         dp[j] = (sum[j+1] - sum[max(0, j-i+1)]) % mod
      }
      for j := 1; j <= k; j++ {
         sum[j+1] = sum[j] + dp[j]
      }
   }
   return dp[k]
}

func max(a, b int) int {
   if a > b {
      return a
   }
   return b
}

总结

Hard题目，动态规划题目，需要分析优化，O(n^3)的时间复杂度容易超时