629.k个逆序对数组

1
2
3
4

输入: n = 3, k = 0
输出: 1
解释: 
只有数组 [1,2,3] 包含了从1到3的整数并且正好拥有 0 个逆序对。

1
2
3
4

输入: n = 3, k = 1
输出: 2
解释: 
数组 [1,3,2] 和 [2,1,3] 都有 1 个逆序对。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

const int MOD = 1e9 + 7;
class Solution {
public:
    int kInversePairs(int n, int k) {
        int dp[1010][1010] = {0};
        dp[0][0 ] = 1;
        for(int i=1;i<=n;i++) {
            //枚举k 的位置
            for(int j=0;j<=k;j++) {
                for(int k=0;k<= min(i-1,j) ;k++) {
                    //个数为 (j-k)
                    dp[i][j] = (dp[i][j] + dp[i-1][j-k]) % MOD;
                }
            }
        }
        return dp[n][k];
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

const int MOD = 1e9 + 7;
class Solution {
public:
    int kInversePairs(int n, int k) {
        int dp[1010][1010] = {0};
        dp[0][0 ] = 1;
        for(int i=1;i<=n;i++) {
            //枚举k 的位置
            for(int j=0;j<=k;j++) {
               long long sum = 0;
               for(int l=j-(i-1);l<=j;++l) {
                   if(l>=0) {
                       sum += dp[i-1][l];
                   }
               }
               dp[i][j] = sum % MOD;
            }
        }
        return dp[n][k];
    }
};