你想，如果用你这种O(1)的转移方程(f[i,j]=f[i-1,j-1]+f[i-1,j])，那么在转移过程中我们在计算f[i,_]前必定需要保留f[i-1,_]上的所有数据，每当计算出来一个f[i,_]上的记录，对应的我可以删除一个f[i-1,_]上的记录，也就是说我们需要保留的数据是O(n)。这样的分析是在i(1->n) j(1->i)上考虑的，但是我们可以进行不严谨的推广（这样比较好理解），抽象地想，如果要有O(1)的转移，那么计算的过程必定是一滴墨水在纸上扩散的过程，是一条线扫出一个面。

所以，我认为空间复杂度在这样的情况下最小是O(n)。

[ 本帖最后由 卧龙孔明 于 2011-3-1 22:59 编辑 ]

这样吧,a[i%2][j] = a[(i-1)%2][j] + a[(i-1)%2][(j-1)];
空间复杂度O(n)

是的，我想单单从复杂度角度看是最理想的情况了。
其实我是想用一些技巧让cpp(C Preprocessor)完成这些任务（仅仅是娱乐），但是因为一些平台相关的问题，我没有去实现。

[ 本帖最后由 卧龙孔明 于 2011-3-1 23:12 编辑 ]

一维数组:
a[2*N]
a[(i%2)*N+j] = a[((i-1)%2)*N+j] + a[((i-1)%2)*N+j-1];

嗯。我也觉得这个复杂度不能再低了。

孔明说的用处理做是什么意思？
是说做好的效果大约是：在预处理阶段就可以把 factorial(n) 替换成对应的数吗？

《java 核心编程》有一道 杨辉三角的题， java是支持变长数组的，
杨辉三角实际应用的时候，就是用变长数组来节省空间。
这种小儿科， 比什么滚动数组差远了，别激动...

我最近在整理文档、IDE、源文件、资源... ，不跟你们讨论啦

时间复杂度和空间复杂度是对立
a[10][5]二维数组就ok

版主 求教！！！516250887