赞
踩
分析:
先考虑如下问题。
求长度为n
,逆序对为m
的排列数量。
可以考虑dp
,dp[i][j]
定义为长度为i
,逆序对为j
的排列数量。
dp[1][0] = 1; //枚举排列长度,或者认为枚举当前需要插到长度为i-1的排列中的数字 for(int i = 1; i <= n; ++i) { for(int j = 0; j <= i * (i + 1) / 2; ++j) { //枚举当前数字插到的位置,一共i个位置,分别可能使逆序对增加0~i-1个 for(int k = 0; k < i; ++k) { if(j >= k) { dp[i][j] += dp[i - 1][j - k]; } } } }
在懂了上述dp
之后,再来考虑本题。主要有两个问题。
dp[i][j]
是否依旧可以这样求,因为上述问题中对于长度为i
的排列,前i-1
个数字确定的,i
一定是最大的,我们只需要考虑它放在哪个位置即可。requirements[i][endi] = cnti
和requirements[j][endj] = cntj
,其中i!=j
。对于第一点,肯定是可以这样求的,一方面我们不需要关心前i-1
个数字是什么,只需要认为我们枚举的第i
个数字是这i
个数字中最大的(类似上述思路)或者是最小的(与最大的等效并且更加方便理解上述dp
的最内层循环)即可,另一方面我们看到至少有一个i
满足endi == n - 1
。
对于第二点,我们只需要在dp
的过程中适当修改。若
∃
e
n
d
j
=
=
i
\exists end_j == i
∃endj==i,则正常求
d
p
[
i
]
[
c
n
t
j
]
dp[i][cnt_j]
dp[i][cntj]的值,而
d
p
[
i
]
[
k
]
=
0
,
k
≠
c
n
t
j
dp[i][k]=0,k\ne cnt_j
dp[i][k]=0,k=cntj。
AC代码
class Solution { public: int numberOfPermutations(int n, vector<vector<int>>& requirements) { const int mod = 1e9 + 7; vector<int> vt(305, -1); for(auto x: requirements) vt[x[0] + 1] = x[1]; vector<vector<int>> dp(305, vector<int>(405, 0)); dp[0][0] = 1; for (int i = 1; i <= n; ++i) { if (vt[i] != -1) { int j = vt[i]; for (int k = 0; k < i; ++k) if (j >= k) dp[i][j] = (dp[i][j] + dp[i - 1][j - k]) % mod; continue; } for (int j = 0; j <= min(400, (1 + i) * i / 2); ++j) { for (int k = 0; k < i; ++k) { if (j >= k) dp[i][j] = (dp[i][j] + dp[i - 1][j - k]) % mod; } } } return dp[n][vt[n]]; } }; //dp数组定义为vector,如果定义为数组,一定记得先memset 0 //(dp[i][j] += dp[i - 1][j - k]) % mod不等价于dp[i][j] = (dp[i][j] + dp[i - 1][j - k]) % mod; //(dp[i][j] += dp[i - 1][j - k]) % mod,模完之后值未赋给任何数。
上述代码已经可以AC
,但是可以进一步优化。
dp[i][j]
的递推过程中,只用到了dp[i-1][j-k]
,故可以通过滚动数组优化空间。k
的循环,我们发现递推公式等价于
d
p
[
i
]
[
j
]
=
∑
k
=
j
−
(
i
−
1
)
j
d
p
[
i
−
1
]
[
k
]
dp[i][j] = \sum_{k=j-(i-1)}^{j} dp[i-1][k]
dp[i][j]=∑k=j−(i−1)jdp[i−1][k],即是dp[i-1]
数组的一个前缀和,故可以预处理出前缀和,使得dp[i][j]
实现O(1)
递推,优化为两层循环。优化后的代码:
class Solution { public: int numberOfPermutations(int n, vector<vector<int>>& requirements) { const int mod = 1e9 + 7; vector<int> vt(305, -1); for(auto x: requirements) vt[x[0] + 1] = x[1]; vector<int> dp(405, 0); vector<int> sum(405, 0); dp[0] = 1; for (int i = 1; i <= n; ++i) { sum[0] = dp[0]; for(int j = 1; j <= min(400, (1 + i) * i / 2); ++j) sum[j] = (sum[j - 1] + dp[j]) % mod; if (vt[i] != -1) { for(int j = 0; j <= min(400, (1 + i) * i / 2); ++j) dp[j] = 0; int j = vt[i]; if(j < i) dp[j] = sum[j]; else dp[j] = (sum[j] - sum[j - i] + mod) % mod; continue; } for (int j = 0; j <= min(400, (1 + i) * i / 2); ++j) { if(j < i) dp[j] = sum[j]; else dp[j] = (sum[j] - sum[j - i] + mod) % mod; } } return dp[vt[n]]; } };
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。