http://acm.hdu.edu.cn/showproblem.php?pid=4055
题意：给一个仅包含‘I','D','?'的字符串，’I'表示前面的数字比后面的数字要小（Increase升序），'D'表示前面的数字比前面的数字要大（Decrease降序），'?'表示有可能是'I'也有可能是'D',长度为n的字符串就有n+1个数字，在这n+1个数字里面，问符合给出的字符串的条件的序列数有多少种。
思路：dp[i][j]的定义：i表示当前枚举到第i个字符（即长度为i+1的时候的序列），j表示当前序列长度为i+1的时候第i+1位插入的数是什么，dp[i][j]表示长度为i+1的序列末尾为j的序列数总共有多少种。
首先需要转化一个思维：即例如前面序列长度为3，假设s[4] = 'D', 那么加入当前的数的时候，即(3, 1, 2)，现在枚举的是dp[4][1]，即要插入1，那么可以当成前面大于等于1(j)的数全部+1，序列就变成(4, 2, 3, 1)，因此可以用前面的来推出后面的。
当s[i]为'I'的时候，插入的数要比前面一位大，因此前面一位是(1~j-1)的时候都可以插入，所以dp[i][j] = dp[i-1][j-1] + ... + dp[i-1][1].
当s[i]为'D'的时候，插入的数要比前面一位小，前面说了，要插入的数j在前面重复的时候，可以把前面的大于等于j的数都+1，所以前面是(j~i)都可以插入(j也是可取的，因为+1就变成j+1了)，dp[i][j] = dp[i-1][j] + ... + dp[i-1][i].
这个式子是可以处理出前缀和的，即每次都把dp[i][j] = dp[i][j-1]这样就可以累加起来了。
而且当前的i只和i-1有关，可以使用滚动数组，还有交C++如果MOD运算过多会超时。
1 #include <bits/stdc++.h> 2 using namespace std; 3 typedef long long LL; 4 #define N 1010 5 const int MOD = 1e9 + 7; 6 LL dp[2][N]; 7 char s[N]; 8 int main() { 9 while(~scanf("%s", s + 1)) { 10 int n = strlen(s + 1); 11 memset(dp, 0, sizeof(dp)); 12 int pre = 0, now = 1; 13 dp[pre][1] = 1; 14 for(int i = 1; i <= n; i++) { 15 for(int j = 1; j <= i + 1; j++) { 16 dp[now][j] = dp[now][j-1]; // 前缀和 17 if(s[i] != 'I') dp[now][j] = (dp[now][j] + (dp[pre][i] - dp[pre][j-1]) + MOD) % MOD; 18 if(s[i] != 'D') dp[now][j] = (dp[now][j] + dp[pre][j-1]) % MOD; 19 } 20 pre ^= now; now ^= pre; pre ^= now; 21 } 22 printf("%lld ", dp[n%2][n+1]); 23 } 24 return 0; 25 }