leetcode-go/hard/629.k-inverse-pairs-array.go

const MOD int = 1000000007

func kInversePairs(n int, k int) int {
	if k < 0 || n*(n-1)/2 < k { // For n, n-1, ... , 2, 1, k = n*(n-1)/2 -> maximum
		return 0
	} else if k == 0 || k == n*(n-1)/2 {
		return 1
	}
	dp := make([][]int, n+1)
	for i := range dp {
		dp[i] = make([]int, k+1)
	}
	// dp[n][k] means kIP(n, k), so:
	// dp[n][k] = dp[n-1][k] + dp[n-1][k-1] + ... + dp[n-1][k-n+1]
	// dp[n][k+1] = dp[n-1][k+1] + dp[n-1][k] + ... + dp[n-1][k+1-n+1]
	// => dp[n][k+1] = dp[n][k] + dp[n-1][k+1] - dp[n-1][k-n+1]
	dp[2][0], dp[2][1] = 1, 1
	for i := 3; i <= n; i++ {
		dp[i][0] = 1
		for j := 1; j <= minInt(k, i*(i-1)/2); j++ {
			dp[i][j] = (dp[i][j-1] + dp[i-1][j]) % MOD
			if j >= i {
				dp[i][j] = (dp[i][j] + MOD - dp[i-1][j-i]) % MOD
			}
		}
	}
	return dp[n][k]
}

func minInt(x, y int) int {
	if x < y {
		return x
	}
	return y
}