题目描述
输入:
n:n是整数1到n的上界,[1, 1000]
k:逆序对的数量,[0, 1000]
输出:
拥有k个逆序对不同排列数组的个数
样例
见原题
算法1
(朴素解法) $O(n^3)$
状态表示:
$f(i,j)$:集合:所有由1-i构成包含j个逆序对的所有排列
i:数值范围上界,[1, 1000]
j:逆序对数量, [0, 1000]
属性:个数
状态计算:
由于是求个数,因此必须划分成不重不漏的若干个子集
以i的位置为划分,考虑第i个数,即数的上界在第k个位置,如k=3
(与数组下标保持一致)时
1 2 3 i 4 … i-1
可以看到逆序对为i与4 … i-1的组合,一共有i-1-k个逆序对;
又因为总共有j个逆序对,所以当扔掉这个i,从i变为i-1时,
$f(i,j)$转移至$f(i-1,j-(i-1-k))$。
又因为i总共有i种放置的可能$(0<=k<=i-1)$,
因此\[f(i,j)=\sum_{l=j-(i-1)}^{j} f(i-1,l)\]
(因为逆序对数量不能小于0,因此j-(i-1)>=0才能进行转移)
C++ 代码
class Solution {
public:
int kInversePairs(int n, int k) {
// 会超时的朴素解法
int mod=1e9+7;
vector<vector<int>> f(n+1,vector<int>(k+1));
f[1][0]=1;
// 已经给出了i=1的边界条件,从i=2开始求
for(int i=2;i<=n;i++)
{
for(int j=0;j<=k;j++)
{
long long sum=0;
for(int l=j-(i-1);l<=j;l++)
//因为逆序对数量不能小于0,因此j-(i-1)>=0才能进行转移
if(l>=0)
sum+=f[i-1][l];
f[i][j]=sum%mod;
}
}
return f[n][k]%mod;
}
};
算法2
(DP优化) $O(n^2)$
观察上述转移方程\[f(i,j)=\sum_{l=j-(i-1)}^{j} f(i-1,l)\]
在求$f(i,j)$时是先迭代i再迭代j,而
\[f(i,j)=f(i-1,j-(i-1))+f(i-1,j-(i-1)+1)+…+f(i-1,j)\]
\[f(i,j+1)=f(i-1,j-(i-1)+1)+…+f(i-1,j)+f(i-1,j+1)\]
因此,可以通过一个变量保存所有数组相加的个数,从而将l的循环时间
复杂度降至O(1),省去一重循环的时间。
C++ 代码
class Solution {
public:
int kInversePairs(int n, int k) {
// 会超时的朴素解法
#ifdef _naive
int mod=1e9+7;
vector<vector<int>> f(n+1,vector<int>(k+1));
f[1][0]=1;
// 已经给出了i=1的边界条件,从i=2开始求
for(int i=2;i<=n;i++)
{
for(int j=0;j<=k;j++)
{
long long sum=0;
for(int l=j-(i-1);l<=j;l++)
//因为逆序对数量不能小于0,因此j-(i-1)>=0才能进行转移
if(l>=0)
sum+=f[i-1][l];
f[i][j]=sum%mod;
}
}
return f[n][k]%mod;
#endif
// 优化解法
int mod = 1e9 + 7;
vector <vector<int>> f(n + 1, vector<int>(k + 1));
f[1][0] = 1;
// 已经给出了i=1的边界条件,从i=2开始求
for (int i = 2; i <= n; i++) {
//注意sum要提出来上一层循环,因为这种解法中需要根据sum之前的值$f(i,j)$推出f(i,j+1)
long long sum = 0;
for (int j = 0; j <= k; j++) {
//注意此时的j已经变成了j'=j+1,因此实质上增加的末项为f(i,j')
sum += f[i - 1][j];
//注意此时的j已经变成了j+1,因此实质上减掉的首项为j-(i-1)=j+1-i=j'-i
if (j - i >= 0)
sum -= f[i - 1][j - i];
f[i][j] = sum % mod;
}
}
return f[n][k] % mod;
}
};