LC 629. K Inverse Pairs Array

https://leetcode.com/problems/k-inverse-pairs-array/

首先这个问题是个动态规划问题，状态方程如下：

考虑n=4的情况，我们如何放置数字4。假设n=3的排列是abc, 有x个inverse pairs, 看看数字4的位置会产生多个个inverse pairs

如果简单地按照这个状态方程计算的话，时间复杂度是O(n^3). 

class Solution:
    def kInversePairs(self, n: int, k: int) -> int:
        # dp[n][k] = dp[n-1][k] + dp[n-1][k-1] + ... dp[n-1][max(k-n+1, 0)]

        dp = [[0] * (k + 1) for _ in range(n + 1)]
        dp[1][0] = 1

        for i in range(1, n):
            for j in range(0, k + 1):
                for off in range(0, i + 1):
                    if (off + j) > k:
                        break
                    dp[i + 1][off + j] += dp[i][j]

        # print(dp)
        return dp[n][k]

如果观察上面方程的话，明显可以感觉到这是一个滑动窗口。

这个滑动窗口计算需要非常小心，因为下标在不断地变化. 

class Solution:
    def kInversePairs(self, n: int, k: int) -> int:
        # dp[n][k] = dp[n-1][k] + dp[n-1][k-1] + ... dp[n-1][max(k-n+1, 0)]
        # 这个状态方程需要计算优化

        MOD = 10 ** 9 + 7

        dp = [[0] * (k + 1) for _ in range(n + 1)]
        dp[1][0] = 1

        for i in range(2, n + 1):
            acc = 0
            for j in range(0, k + 1):
                # dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1] + ... dp[i - 1][j - i + 1] + (dp[i-1][j-i])
                acc += dp[i - 1][j]
                if j >= i:
                    acc -= dp[i - 1][j - i]
                acc = acc % MOD
                dp[i][j] = (acc + dp[i][j]) % MOD

        # print(dp)
        return dp[n][k]