看书上讲动态规划或者备忘录的例题时候总是忽略空间限制．有时候问题范围大的很，例如我遇到的一到题如果申请的话是３维数组，每个上限是３００，都要３００的３次方的空间，而其实大部分都浪费了．
如果我使用一维顺次结构储存计算中的结果，在每次取结果的时候还要查找，耗费O(n)的时间，这样是否可行呢？
请有经验的前辈谈谈．

能帮我看看题当然是太好了.
感谢前辈.
这是题目:
The 2006 FIFA World Cup Final was held in Berlin, Germany on July 9th, 2006, with France against Italy. Both France and Italy are the conquerors of the European soccer field. Soccer fans from all over the world came to Berlin Olympic Stadium to celebrate this world's biggest soccer party. In front of the ticket booth outside the stadium, we observed something interesting:

The ticket for the final match costs $50. There are m fans in the line having only $50 bill and n fans having only $100 bill. The ticket booth does not hold any changes. Please calculate in how many ways can these (m+n) soccer fans all get their tickets without the ticket booth running out of changes.

Input

Every pair of data consists of two non-negative integers m, n(not exceed 300), separated by a space. The last line of the input is a line containing two zeros.

Output

For every pair of data, output the number of ways the fans could line up.

Sample Input

1 1
1 2
3 0
0 0

Sample Output

1
0
1

我一开始用递归写了一个,发现到了20,20就已经出不来了,改用回溯的也一样.
考虑到里面有大量重复的计算,我想用三维S(已有的$50数量),M,N来保存一个结果.
所以才在这里问这个.

顺便提一下,十分想和"乌鸦丘比特"联系一下,记得一年前我在这论坛就给你发过一个E-mail,问了点问题,可惜没回.
如果你愿意请加我QQ354280135,以后想问些东西.

十分感谢~谢谢
但我不太明白什么是"滚动数组"?

[此贴子已经被作者于2006-8-6 21:15:34编辑过]

完全明白了,谢谢
顺便问问,我想要些学习算法的资源,网站,论坛,带解析的习题什么的,适合初学的人的.

[此贴子已经被作者于2006-8-6 22:28:39编辑过]

恩,我倒是有一本算法的书在看,也有竞赛辅导的.
最后还是十分感谢乌鸦.

如果能找到这些学习资料当然是要好好学学了,我对节省很感兴趣.