题目描述
903. Valid Permutations for DI Sequence
We are given S
, a length n
string of characters from the set {'D', 'I'}
. (These letters stand for “decreasing” and “increasing”.)
A valid permutation is a permutation P[0], P[1], ..., P[n]
of integers {0, 1, ..., n}
, such that for all i
:
- If
S[i] == 'D'
, thenP[i] > P[i+1]
, and; - If
S[i] == 'I'
, thenP[i] < P[i+1]
.
How many valid permutations are there? Since the answer may be large, return your answer modulo 10^9 + 7.
Example 1:
Input: "DID"
Output: 5
Explanation:
The 5 valid permutations of (0, 1, 2, 3) are:
(1, 0, 3, 2)
(2, 0, 3, 1)
(2, 1, 3, 0)
(3, 0, 2, 1)
(3, 1, 2, 0)
Note:
1 <= S.length <= 200
S
consists only of characters from the set{'D', 'I'}
.
题意:我们给出 S
,一个源于{'D', 'I'}
的长度为n
的字符串 。(这些字母代表 “减少” 和 “增加”。)
有效排列 是对整数 {0, 1, ..., n}
的一个排列 P[0], P[1], ..., P[n]
,使得对所有的 i:
如果 S[i] == 'D'
,那么 P[i] > P[i+1]
,以及;
如果S[i] == 'I'
,那么P[i] < P[i+1]
。
有多少个有效排列?因为答案可能很大,所以请返回你的答案模10^9 + 7
.
算法1
(动态规划) $O(n^3)$
题解1:动态规划。这道题首先给出了最后答案很大需要取模,所以这道题很明显是一道计数DP类的问题,接下来我们需要寻找状态表示和状态转移。很朴素的想法就是dp[i]
代表了[0 : i]
这i + 1
个元素满足前i
个序列的方案数,但是这样,我们无法直接进行状态转移,因为下一个元素放置什么除了取决于上升下降关系外,还取决于当前最后一个数字是多少。基于此,我们可以提出这样的状态表示:
dp[i][j]
代表将[0 : i]
这i + 1
个元素满足前i
个DI序列并且最后一个元素是j
的方案数,这里很明显j <= i
。
接下来我们考虑状态转移:
考虑dp[2][1]
代表的是前三个元素并且末尾是1
的方案数,我们从中任取一种方案,2,0,1
,接下来我们需要放置元素3
了。
假设此时s[2] = D
。这是我们显然不能直接把3
放在后面。考虑当前最后一个元素为1,那么我们可以把序列中所有大于等于1的元素都加上1得到序列3,0,2
(这个时候是不会改变当前序列的大小关系的),这个时候,我们再把1添加到序列末尾得到3,0,2,1
。同样的我们可以把序列中所有大于等于0的元素都加上1得到序列3,1,2
,这时候我们再把0添加到末尾,得到3,1,2,0
。进一步的我们可以得到,对dp[i - 1][k]
中的所有方案,我们都可以将该序列中所有大于等于j(0 <= j <= k)
的元素加上1,并在末尾添加一个j
得到dp[i][j]
中的一种方案。也就是dp[i][j]
可以由所有的j <=k < i
对应的dp[i - 1][k]
生成。
假设此时s[2] = I
。这时候我们可以直接把3放在后面。考虑当前最后一个元素为1,我们同样的可以把序列中所有大等于2的元素都加上1得到3,0,1
,再把2放在序列末尾得到3,0,1,2
。进一步的,我们可以得到对于dp[i - 1][k]
中的所有方案,我们都可以把该序列中所有大于等于j(k < j <= i)
的数字都加上1,并在末尾添加一个j
得到dp[i][j]
中的一种方案。也就是dp[i][j]
可以由所有的0 <= k < j
对应的dp[i - 1][k]
生成。
基于此,我们的状态转移可以写成:
当s[i - 1] = 'I'
时,$dp(i,j) = \sum _{k = 0}^{k =j - 1}dp(i - 1,k)$
当s[i - 1] = 'D'
时,$dp(i,j) = \sum _{k = j}^{k =i - 1}dp(i - 1,k)$
状态初始化:dp[0][0] = 1
,刚开始只能把0放在起始位置上。
时间复杂度分析:$O(n^3)$
C++ 代码
int numPermsDISequence(string s) {
int n = s.length(),mod = 1000000007,res = 0;
int dp[n + 1][n + 1] = {};
dp[0][0] = 1;
for(int i = 1 ; i <= n ; i ++)
{
for(int j = 0 ; j <= i ; j ++)
{
if(s[i - 1] == 'D')
{
for(int k = j ; k <= i ; k ++)
dp[i][j] = (dp[i][j] + dp[i - 1][k]) % mod ;
}else
{
for(int k = 0 ; k < j ; k ++)
dp[i][j] = (dp[i][j] + dp[i - 1][k]) % mod;
}
}
}
for(int i = 0 ; i <= n ; i ++)
res = (res + dp[n][i]) % mod;
return res;
}
算法2
(优化版本动态规划) $O(n^2)$
题解2:动态规划优化。延续上述的思路,但是我们发现我们的重复计算太多了。
当s[i - 1] == 'D'
的时候:
dp[i][j] = dp[i - 1][j] + dp[i - 1][j + 1] + dp[i - 1][j + 2] + ... + dp[i][i - 1]
dp[i][j + 1] = dp[i - 1][j + 1] + dp[i - 1][j + 2] + ... + dp[i][i - 1]
dp[i][j] = dp[i][j + 1] + dp[i - 1][j]
基于此,我们需要从后往前计算,而且从i - 1开始计算就可以了,一方面是当s[i - 1] = 'D'的时候,i不可能出现在最后一个位置上,同时也避免了j + 1越界。
当s[i - 1] = 'I'
的时候
dp[i][j] = dp[i - 1][0] + dp[i - 1][1] + ... + dp[i - 1][j - 1]
dp[i][j - 1] = dp[i - 1][0] + dp[i - 1][1] + ... + dp[i - 1][j - 2]
dp[i][j] = dp[i][j - 1] + dp[i - 1][j - 1]
基于此,我们需要从前往后计算,而且从1开始计算就可以了,一方式是当s[i - 1] = 'I'的时候,0不可能出现在最后一个位置上,同时也避免了j - 1越界。
时间复杂度:$O(n^2)$
C++ 代码
int numPermsDISequence(string s) {
int n = s.length(),mod = 1000000007,res = 0;
int dp[n + 1][n + 1] = {};
dp[0][0] = 1;
for(int i = 1 ; i <= n ; i ++)
{
if(s[i - 1] == 'D')
{
for(int j = i - 1 ; j >= 0 ; j --)
dp[i][j] = (dp[i][j + 1] + dp[i - 1][j]) % mod;
}else
{
for(int j = 1 ; j <= i ; j ++)
dp[i][j] = (dp[i][j - 1] + dp[i - 1][j - 1]) % mod;
}
}
for(int i = 0 ; i <= n ; i ++)
res = (res + dp[n][i]) % mod;
return res;
}
算法3
(分治/区间动态规划) $O(n^3)$
题解3:分治算法(区间动态规划)。
状态表示:dp[i][j]
表示填充区间p[i:j]
共j - i + 1
个数的方案数。不考虑具体数字,只考虑数字之间的大小关系。
状态初始化:dp[i][i] = 1
,区间内只有一个数字,数字大小关系是唯一确定的。最终返回dp[0][n]
即可。
状态转移:我们考虑枚举当前区间最大的数可以放在哪些位置。我们知道控制区间dp[i][j]
的是序列s[i:j - 1]
。
如果s[i] = 'D'
,那么最大的元素可以放在p[i]
上。dp[i][j] += dp[i + 1][j]
如果s[j - 1] = 'I'
,那么最大的元素可以放在p[j]
上。dp[i][j] += dp[i][j - 1]
每一个区间其实类似于一个摆动序列,最大元素只可能放在峰值的位置上。所以我们枚举[i + 1:j - 1]
中每一个位置k
。如果s[k - 1] = 'I' and s[k] = 'D'
,那么当前位置就是一个峰值。那么现在数组被划分成了两个部分s[i:k - 1]
和s[k + 1,j]
。区间长度为j - i + 1
,除去最大的那个元素,那么还剩j - i
个元素,我们需要从这j - i
个元素中挑选出k - i
个元素放在左半区间。这样我们既可以求解两个子区间了。
dp[i][j] += dp[i][k - 1] * dp[k + 1][j] * C(j - i,k - i) if s[k - 1] = 'I' and s[k] = 'D' for k in [i + 1:j - 1]
。
这里我们介绍一下组合数的动态规划求解:
状态表示:C[i][j]
代表从i
个数选择j
个数的所有方案数。
状态初始化:C[i][0] = 1
代表,从i
个数选择0个数只有一种情况什么都不选。
状态转移:C[i][j] = C[i - 1][j - 1] + C[i - 1][j]
。考虑从i
个数中选择j
个数的方案数,我们考虑最后一个数字选不选,如果最后一个数字选的话,那么相当于还需要从前i - 1
个数字中选择j - 1
个数字,如果最后一个数字不选的话,相当于还需要从前i - 1
个数字中选择j
个数字。
时间复杂度分析:$O(n^3)$
int numPermsDISequence(string s) {
int n = s.length(),mod = 1000000007,res = 0;
int dp[n + 1][n + 1] = {};
int C[n + 2][n + 2] = {};
for(int i = 0 ; i <= n ; i ++)
dp[i][i] = 1;
for (int i = 0; i <= n + 1; i++) {
C[i][0] = 1;
for (int j = 1; j <= i; j++)
C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % mod;
}
for(int len = 2 ; len <= n + 1 ; len ++)
{
for(int i = 0 ; i + len - 1 <= n ; i ++)
{
int j = i + len - 1;
if(s[i] == 'D')
dp[i][j] = (dp[i][j] + dp[i + 1][j]) % mod;
if(s[j - 1] == 'I')
dp[i][j] = (dp[i][j] + dp[i][j - 1]) % mod;
for(int k = i + 1 ; k <= j - 1 ;k ++)
if(s[k - 1] == 'I' && s[k] == 'D')
dp[i][j] = (dp[i][j] + (1ll * C[len - 1][k - i]) * dp[i][k - 1] % mod * dp[k + 1][j] % mod) % mod;
}
}
return dp[0][n];
}
写在最后 ,分治tag下的题都好难啊