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

今天这道题的名字叫做栈(想看原题可以到《动态规划小山坡》找到),题目是这样描述的,有两个序列中间有一个栈,其中一个序列有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的效率要明显高很多。

dp

#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

#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;
}