Участник:Plague rat/K Inverse Pairs Array

Материал из DISCOPAL
Перейти к: навигация, поиск

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

class Solution:
    def kInversePairs(self, n: int, k: int) -> int:
        modulo = 10 ** 9 + 7
        inversePairs = [[0] * (k + 1) for i in range(n + 1)]
 
        inversePairs[0][0] = 1
        for i in range(1, n + 1):
            for j in range(k + 1):
                if j == 0:
                    inversePairs[i][j] = 1
                else:
                    inversePairs[i][j] = (inversePairs[i][j - 1] + inversePairs[i - 1][j]) % modulo
                    if j >= i:
                        inversePairs[i][j] = (inversePairs[i][j] - inversePairs[i - 1][j - i]) % modulo
 
        return inversePairs[n][k]