动态规划之栈

今天在琢磨一道动态规划类型的题，感觉很不好，完全想不到思路，还是没有找到精髓，慢慢来吧，不断做，不断总结，相信总有一天能掌握的。

今天这道题的名字叫做栈（想看原题可以到《动态规划小山坡》找到），题目是这样描述的，有两个序列中间有一个栈，其中一个序列有n个数，需要通过这个栈，将这个每个数移动到另一个序列中，移动到栈中的数(也就是相当于push)可以立马弹出(对应pop)，也可以选择不弹出，可以继续往栈中存放数字，问可以生成多少种不同的序列。

起初我想的可简单了，这不就是将n个数进行全排列，而且问的只是有多少种不同的序列，也就是求一个具体的数目，那么我完全可以用数学公式来进行求啊，n*(n-1)/2就可以得出来结果，结果20分，我还想了很久，我觉得这样想的没有问题啊，最后发现这样想确实是不对的，因为压入栈中得数，栈底的数不可能比栈顶的数先出来，所以，这样的想法就有问题。

发现这样的问题之后，我就开始要朝别的想法出发了，从序列只有一个数列举到序列只有三个数，发现到n=3的时候还可以骗骗自己，然后到n=4的时候就比较复杂了，找不到上一步和下一步的一个关系，也就是所谓的状态转移方程，就跟汉诺塔一样，你无法将所有的结果用大脑想出来，但是我们可以想这一个结果要经过怎样的方法公式运算出来。

这道题有三种状态会不断更新，对应两种操作。三种状态分别是序列A，栈B，序列C，在数字不断在它们三者之间不断进行转换的时候，他们的所包含的数字个数都会更新的。对应的两种操作，push操作实际上实在栈B和序列C之间进行操作（原序列就是放在C中的），当进行入栈操作的时候，序列C数字的个数将会减一，栈B的个数将会加一；当进行出栈操作的时候，实际上是在序列A和栈B之间进行操作的，此时栈B的数字个数将会减一，序列A的个数将会加一。

发现没有，我们不需要考虑你中间是咋运行的，我只要最后的一个结果，那就是序列C中的数全部都转移到了序列A中，状态转移方程:F[i][j]=F[i-1][j]+F[i+1][j-1],解释一下i是代表栈B中的数字个数，j是代表序列C中数字的个数，那么通常的情况下，是不是只有这两种操作，只要能够算出两种操作的次数，那么就可以一层一层的算出来结果（特殊情况下还需要特殊处理），这个是不是和汉诺塔一样，我不需要知道你中间是怎么运行的，你只需要给我一个结果就可以了。

下面就要考虑一下边界条件了，当栈B中的数字个数为零时，是不可以进行出栈操作的（pop），当序列C中的数字个数为零时，不可以进行入栈操作（push），当序列C中的数全部转移到序列A中的时候，也就是得到了一种结果，要终止此次操作，这些都是边界条件。

下面就是开始写代码了，我是用了两种方法，一种是dfs，一种是dp，对比了一下两种代码，发现随着n的增大，dp的效率要明显高很多。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29


#include <iostream>
using namespace std;
int arr[20][20];//两个下标分别代表栈B数字的个数和序列C数字的个数
int main()
{
    int n;//序列C中数字的个数
    cin >> n;
    for (int j = 0; j <= n; j++)//这里为什么要j在第一层循环？我想的是出栈之前必须要进行入栈
    {
        for (int i = 0; i <= n; i++)
        {
            if (j == 0)//当序列C中没有数字了，那把栈中所有的数字移动到序列A中就结束了
            {
                arr[i][0] = 1;//因为从栈中出来的数只有一种结果
            }
            else if (i == 0)
            {
                arr[0][j] = arr[1][j - 1];//当栈中没有数字时，要将序列C中的一个数字移动到栈B中
            }
            else
            {
                arr[i][j] = arr[i - 1][j] + arr[i + 1][j - 1];//这种就是通常的情况了
            }
        }
    }
    cout << arr[0][n];//要将序列C中的数字全部移动到序列A中
    system("pause");//这个代码是在vscode运行需要这条语句，其他地方不需要
    return 0;
}

dfs

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27


#include <iostream>
using namespace std;
int t = 0;
void dfs(int n, int x, int y, int z)
{
    if (y < 0 || z < 0)//边界条件
    {
        return;
    }
    if (x == n)//找到一种结果
    {
        t++;
        return;
    }

    dfs(n, x, y + 1, z - 1); //对应入栈操作
    dfs(n, x + 1, y - 1, z); //对应出栈操作
}
int main()
{
    int n;//初始序列C中的数字个数
    cin >> n;
    dfs(n, 0, 0, n);
    cout << t;//所有可能输出的数列个数
    system("pause");//运行时需要删除
    return 0;
}