[leetcode]2552.统计上升四元组.题解O(n^2)xiaodangao

原题链接：统计上升四元组
动态规划：
其中 $f[i][j]$ 代表的是截止到当前下标为 $i$ 的数组下，大于等于 $j$ 的个数，维护的话也是非常简单的一个线性 $dp$ ，可知 $f[i][j] = f[i-1][j]$ 当前下标下大于等于 $j$ 的个数是大于等于下标为 $i-1$ 状态下大于等于 $j$ 的个数的。如果 $nums[i] \ge j$ 那么很明显 $f[i][j]$ 要在 $f[i-1][j]$ 的基础上加1。
维护好 $f[i][j]$ 之后的工作就很简单了，枚举中间两个逆序，假设下标为 $j,k$ 那么我们分别要寻找：
$x1：$ 下标不超过 $j$ 且小于 $nums[j]$ 的个数
$x2：$ 下标超过 $k$ 且大于 $nums[i]$ 的个数
CPP代码如下

class Solution {
public:
    #define ll long long 
    int idx = 0;

int f[4010][4010];
long long countQuadruplets(vector<int>& nums) {
    int len = nums.size();
    int n = len;
    len-=1;
    //f[i][j] 大于等于j的个数
    for(int i=nums[0];i>=0;--i)f[0][i] = 1;
    for(int i=1;i<=len;++i){
        for(int j=0;j<=n;++j){
            f[i][j] = f[i-1][j];
            if(nums[i] >= j)f[i][j]++;
        }
    }
    ll ans = 0;
    for(int i=1;i<len;++i){
        for(int j=i+1;j<len;++j){
            if(nums[i] < nums[j]){
                continue;
            }
            int x1 = i+1-f[i][nums[j]];
            int x2 = n-nums[i]+1-f[j][nums[i]];
            ll res =(ll) x1 * x2;
            ans += res ;
        }
    }
    return ans ;
}
};

本文采用署名-非商业性使用-相同方式共享 4.0 国际许可协议，转载请注明出处。