8.27 - hard - 109
2017-08-28 本文已影响0人
健时总向乱中忙
629. K Inverse Pairs Array
递推公式如下
f(n,k) = sum(f(n-1,i)), where max(k-n+1,0) <= i <= k
f(0,k) = 0
f(n,0) = 1
def kInversePairs(self, n, k):
dp = [1] + [0] * k
for i in range(2, n + 1):
for j in range(1, k + 1): dp[j] += dp[j - 1]
for j in range(k, 0, -1): dp[j] -= j - i >= 0 and dp[j - i]
return dp[k] % (10**9 + 7)
