629. K个逆序对数组

两个算法100倍的差别。。
我要好好学算法QAQ

f[i][j]：用数字1~i，构成j个逆序对的方案数量

dp（暴力）

这傻逼写法我先试试，结果居然过了，三个循环复杂度有1e9

const int MOD = 1e9+7;
typedef long long ll;

class Solution {
public:
    int kInversePairs(int n, int k) {
        ll f[n+10][k+10];
        memset(f,0,sizeof f);
        f[0][0]=1;
        for(int i=1;i<=n;i++){
            for(int base=0;base<=k;base++){
                for(int j=0;j<=i-1;j++){
                    if(j+base<=k){
                        f[i][j+base]+=f[i-1][base];
                        f[i][j+base]%=MOD;
                    }
                }
            }
        }
        return f[n][k];
    }
};

dp + 前缀和优化

const int MOD = 1e9 + 7;
typedef long long ll;

class Solution {
 public:
  int kInversePairs(int n, int k) {
    ll f[n + 10][k + 10];
    memset(f, 0, sizeof f);
    f[0][0] = 1;
    for (int i = 1; i <= n; i++) {
      ll sum[k + 10];
      memset(sum, 0, sizeof sum);
      for (int j = 0; j <= k; j++) {
        ll right = (j - 1 >= 0) ? sum[j - 1] : 0;
        sum[j] = (f[i - 1][j] + right) % MOD;
      }
      for (int j = 0; j <= k; j++) {
        ll right = (j - i >= 0) ? sum[j - i] : 0;
        ll cur = sum[j] + MOD - right;
        f[i][j] = cur % MOD;
      }
    }
    return f[n][k];
  }
};