Today's Challenge

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

K Inverse Pairs Array - LeetCode

계속 DP 관련 문제가 나옴.
DP는 참.... 풀기가 어렵네 ㅠㅠ

class Solution:
    def kInversePairs(self, n: int, k: int) -> int:
        m = 10**9 + 7
        
        dp = [0] * (k+1)
        dp[0] = 1
        
        for i in range(n):
            ddp = []
            s = 0            
            for j in range(k+1):
                s += dp[j]
                if j >= i + 1:
                    s -= dp[j - i - 1]
                s %= m
                ddp.append(s)
            dp = ddp
        return dp[-1]