给定一个初始为空的栈，和n个操作组成的操作序列，每个操作只可能是出栈或者入栈。
要求在操作序列的执行过程中不会出现非法的操作，即不会在空栈时执行出栈操作，同时保证当操作序列完成后，栈恰好为一个空栈。
求符合条件的操作序列种类。
例如，4个操作组成的操作序列符合条件的如下：
入栈，出栈，入栈，出栈
入栈，入栈，出栈，出栈
共2种。
思路
1. Leetcode 上有道类似的题目, 那道题求得是括号的总类, 当初用的是搜索法
2. 搜索法超时, 分治法没想起什么好办法, 动规没头绪
3. dp[i][j] (i>=j) 表示入栈 i 次出栈 j 次 的种类数
4. dp[i][j] = dp[i-1][j] + dp[i][j-1]. 状态转移方程写出这样的依据应该在于讨论最后一位分别是 '(' 和 ')' 的情况. 就像 剑指offer 铺地板那题类似. 比如 dp[3][2], 当最后一位确定是 '(' 时, dp[3][2] = dp[2][2]; 当确定为 ')' 时, dp[3][2] = dp[3][1]. 如此看来, 这道题和自己以前做过的很多题目类似, 比如爬台阶, 比如方格寻路等等. 这些题目的共同特点是根据最后的状态位递推前面的所有可能性.
5. 会看 leetcode 对应那题, 发现那道是打印路径, 所以搜索法并没超时
代码 未能通过九度测试
#include <iostream> #include <stdio.h> #include <memory.h> using namespace std; int dp[1200][1200]; int find(int a, int b) { if(a < b) return 0; if(dp[a][b] != 0) return dp[a][b]; if(a == 0 || b == 0) return 0; int res = find(a-1,b) + find(a,b-1); if(res >= 1000000007 ) res = res%1000000007; return (dp[a][b] = res); } int main() { freopen("testcase.txt", "r", stdin); int n; memset(dp, 0, sizeof(dp)); for(int i = 0; i < 1010; i ++) dp[i][0] = 1; dp[1][1] = 1; while(scanf("%d", &n) != EOF) { int res = find(n/2,n/2); printf("%d ", res); } return 0; }