629. K 个逆序对数组

解法一：动态规划

当前 n 个数，寻找 k 个逆序对。

• 假设最大数也就是 n 在第一位，那么这时候包含 n 的逆序对会有 n-1 个，那么其他 n-1 个数需要凑出来 k-(n-1) 个逆序对才能满足条件
• 假设最大数 n 在第二位，那么这时候包含 n 的逆序对会有 n-2 个，那么其他 n-1 个数需要凑出来 k-(n-2) 个逆序对才能满足条件
• 以此类推
• 假设最大数 n 在最后一位，那么这时候包含 n 的逆序对会有 0 个，那么其他 n-1 个数需要凑出来 k-n 个逆序对才能满足条件

所以可以得到：


所以得

几个需要注意的点：

• 需要考虑 k < n 的情况
• 需要考虑到 dp[i][j-1] + dp[i-1][j] - dp[i-1][j-i] 这个减法可能会出现负数

  func kInversePairs(n int, k int) int {
    const MOD = 10e8 + 7
    dp := make([][]int, n+1)
    for i := range dp {
        dp[i] = make([]int, k+1)
    }
    dp[1][0] = 1
    for i := 2; i <= n; i++ {
        dp[i][0] = 1
        for j := 1; j <= k; j++ {
            if j >= i {
                dp[i][j] = (dp[i][j-1] + dp[i-1][j] - dp[i-1][j-i] + MOD) % MOD
            } else {
                dp[i][j] = (dp[i][j-1] + dp[i-1][j]) % MOD
            }
        }
    }
    return dp[n][k]
  }