题目

给出两个整数 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 = 1000000007func 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 = 1000000007func 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)的时间复杂度容易超时