宁宁考虑的是这样一个问题：一个操作数序列，1,2,\ldots ,n1,2,…,n（图示为 1 到 3 的情况），栈 A 的深度大于 nn。

现在可以进行两种操作，

  1. 将一个数，从操作数序列的头端移到栈的头端（对应数据结构栈的 push 操作）
  2. 将一个数，从栈的头端移到输出序列的尾端（对应数据结构栈的 pop 操作）

使用这两种操作，由一个操作数序列就可以得到一系列的输出序列，下图所示为由 1 2 3 生成序列 2 3 1 的过程。

输入格式

输入文件只含一个整数 n（1<=n<=18）

输出格式

输出文件只有一行，即可能输出序列的总数目。

输入输出样例

输入 #1复制

1
3

输出 #1复制

1
5

思路分析

根据题目分析，很明显是一个“特殊”的全排列的问题，但是我们不能用简单的递归来做。

用 i 代表待排数，j表示栈内数，

1
int f[][] = new int[20][20]   //该数组代表序列的数量

数据有四种情况：

  • 第一种是待排数 i 中为0，则直接返回1，意思即增加一种排序
  • 一种是如果栈内不为空，且待排数中没有数了，则j-1出栈。
  • 一种情况就是同时入栈和同时出栈 即 i-1 和 j+1。

除此之外一种情况是若f数组中的数不为0 则应该直接返回该数 避免重复计算

实现代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class g23 {
    public static void main(String[] args) {
     Scanner scanner = new Scanner(System.in);
      int f[][]=new int[20][20];
      int n = scanner.nextInt();
        int dfs = dfs(n, 0, f);
        System.out.println(dfs);
    }
    public static int  dfs(int i, int j,int f[][]){
        //i 和 j 分别 代表待排队列和栈内队列
      if (f[i][j]!=0)return f[i][j]; //若不等于0 则返回队列数 
         if (i==0){
             return 1;                //若待排数i=0 则直接返回1 代表增加一个排序列
         }
                                       //以下有两种情况
         if (j>0){                    //如果栈内数大于0  且待排数中没有数了 则j-1 即出栈
             f[i][j]+=dfs(i,j-1,f);
         }
         f[i][j]+=dfs(i-1,j+1,f);   // 还有一种情况就是同时入栈和同时出栈 即 i-1和j+1
         return f[i][j];
    }
}

总结：DFS与动态规划思想