seo平台怎么样/关键词优化排名哪家好

思路：
引用一篇不错的推导。

由于dp[n, k] 仅由dp[n-1, …] 和 dp[n, …] 转移而来，因此可以对动态规划使用的空间进行优化，即使用两个一维数组交替地进行状态转移，空间复杂度从O(nk)降低为O(k).用dp[j] 表示当前数字i 构成j个逆序对。

时间复杂度O(nk).

code:

class Solution:def kInversePairs(self, n: int, k: int) -> int:mod = int(1e9) + 7# dp[n,k] = dp[n, k-1] + dp[n-1, k] - dp[n-1, k-n]# 由于dp[n, k] 仅由dp[n-1, ..] 和 dp[n, ..] 转移而来，因此可以对动态规划使用的空间进行优化，# 即使用两个一维数组交替地进行状态转移，空间复杂度从O(nk)降低为O(k).# 用dp[j] 表示当前数字i 构成j个逆序对。dp = [1] + [0] *kfor i in range(1, n+1):g = [1] + [0] * (k)for j in range(k+1):g[j] = (g[j-1] if j - 1 >= 0 else 0) + dp[j] - (dp[j-i] if j - i >= 0 else 0)g[j] %= moddp = greturn dp[k]

参考题解