629. K Inverse Pairs Array.txt

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

class Solution {
public:
    int kInversePairs(int n, int k) {
        int dp[1001][1001] = {};
        dp[0][0] = 1;
        int mod = 1e9 + 7;
        for (int i = 1; i <= n; ++i) {
            dp[i][0] = 1;
            for (int j = 1; j <= k; ++j) {
                dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % mod;
                int range = max(j - (i - 1), 0);
                if (j - i >= 0)
                    dp[i][j] = (dp[i][j] - dp[i - 1][j - i] + mod) % mod;
            }
        }  
        
        return dp[n][k];
    }
};