题目链接:Click here~~
题意:
给一个字符串,'I' 和 'D‘ 代表排列中递增 or 递减,? 代表均可。
求满足这种条件的排列的方案数。
解题思路:
dp[i][j] 表示长度为 i ,以 j 为结尾的排列的方案数。
如果 str[i-1] == ’I‘ ,那么 dp[i][j] = dp[i-1][j-1] + dp[i-1][j-2] + ... + dp[i-1][1]。
如果 str[i-1] == 'D',那么 dp[i][j] = dp[i-1][i-1] + dp[i-1][i-2] + ... + dp[i-1][j]。
第一个式子比较好理解,只要在长度为 i-1 且结尾数字小于 j 的排列后面加个 j 就好了。
第二个式子,只要在长度为 i-1 且结尾数字大于等于 j 的排列中,把大于等于 j 的数字全部加1(不影响之前的递增和递减情况),后面再加个 j 就行了。
转移的复杂度可以通过用 sum 数组记录前缀和优化到 O(1)。
其实还可以用滚动数组优化空间复杂度。不贴了。
#include <stdio.h> #include <string.h> #include <algorithm> using namespace std; const int N = 1e3 + 2; const int mod = 1e9 + 7; int dp[N][N],sum[N][N]; char str[N]; int main() { dp[1][1] = sum[1][1] = 1; while(~scanf("%s",str+1)) { int n = strlen(str+1) + 1; for(int i=2;i<=n;i++) { for(int j=1;j<=i;j++) { if(str[i-1] == 'I') dp[i][j] = sum[i-1][j-1]; else if(str[i-1] == 'D') dp[i][j] = (sum[i-1][i-1] - sum[i-1][j-1] + mod) % mod; else dp[i][j] = sum[i-1][i-1]; sum[i][j] = (sum[i][j-1] + dp[i][j]) % mod; } } printf("%d\n",sum[n][n]); } return 0; }