- 论坛徽章:
- 0
|
看过下那个 出栈问题的解法, 直接用个 C( )( ) 不是很懂,
我自己后来想了想,把问题归结为 f( n , m ) , f( n , m ) 表示 当前栈里面有n个元素,还有m个元素准备压栈情况下 的所有可能的序列,当然, n+m 个元素应该是不相同的。
所以题目的求有5个元素进栈出栈得到的序列可以表示为 f( 0 , 5 ) == f( 1 , 4 );
f( n , m ) = f( n-1 , m ) + f( n+1 , m -1 ); // <- 得到递推公式,里面有重叠的子问题,这样的递推应该是可以动态规划吧,算法不是很好,以后加强下。
然后画画矩阵: n x m
f( 0 , 0 ) == 0 ;
f( x != 0 , 0 ) == 1 的,
f( 0 , m ) == f( 1 , m-1 ) 的
注意那个递推公式的含义, 头顶的 + 左下 = 自己位置的
0 1 2 3 4 5 6
0 0 1 2 5 14
1 1 2 5 14 42
2 1 3 9 28
3 1 4 14
4 1 5
5 1
这样能得到 f( 0 , 5 ) == f( 1 , 4 ) == 14 + 28 = 42;
但是需要空间比较大,而复杂度应该O( m*n ), 挺糟糕的,但是如何将那个函数化简下,得到更低的复杂度,目前还是没能力哎。。 |
|