629. K Inverse Pairs Array

[namespace-io]

这题的递推数列很好找
就是将最大的在剩下的数字中从左往右移动
假定原来n个数字，现在n+1加进去，对于原来的n个数字而言有n个空槽
A(n+1,k)= A(n，k) + A(n, k - n)，如果暴力就是n^2*k,但是同一层的也能递推，这个就很简单了
但是 我在想 这种应该是有数学推导的直接 推导出来，注意做减法的时候结果可能为负，加上mod在取mod
滚动数组减空间

class Solution {
public:
    int kInversePairs(int n, int k) {
        vector<vector<int>> v(2, vector<int>(k + 1, 0));
        if(n * (n - 1) < 2 * k) return 0;
        for(int i = 1; i <= k; i++) v[1][i] = 0;
        v[1][0] = 1;
        v[0][0] = 1;
        int mod = 1000000007;
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= k; j++){
                v[(i+1)%2][j] = (v[(i+1)%2][j-1] + v[i%2][j]) % mod;
                if(j - i - 1 >= 0) v[(i+1)%2][j] = (v[(i+1)%2][j] - v[i%2][j-i-1] + 1000000007) % mod;
               
            }
        }
        
        return v[(n)%2][k];
    }
};