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

可以的。。。实际可以放在HASH表中。。。实现查找复杂度为o(1)

查找用hash，其实还可以用二叉排序树拉一类的东西。有一些题目可以用滚动数组降低空间复杂度.
不过说老实话，我好象还没碰到状态要用特别的数据结构来存的题目，楼主把题目发上来看看？

能帮我看看题当然是太好了.
感谢前辈.
这是题目:
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,以后想问些东西.

定义d[m][n]为问题(m,n）的解//应该能够看懂吧
那我们想办法把问题（m,n)转化到某个子问题.
（1）当m<n的时候显然d[m][n]=0;
（2）其余情况：
一:如果最后一个人拿50元则可能的情况为d[m-1][n]*m(乘m是因为最后一个人可以是m个人中的任意一个)，
二：如果最后一个人拿100元则可能的情况为d[m][n-1]*n
注意情况一只有在m>n的时候才可以出现。到这里可以得到动态转移方程

d[m][n]=
0 :m<n
d[m][n-1]*n :m=n
d[m][n-1]*n+d[m-1][n]*m:m>n
m! :n=0


由这个动态转移方程就可以递推求出所需要的解答,这里的空间需求是O（N^2），其实注意到d[m][n]依赖的状态无非是d[m][n-1]和d[m-1][n]，这样可以用滚动数组来把空间需求降为O(N^2);

值得注意的是规模到300的话数据已经很大，不是一般变量能够承受的

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

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

滚动数组嘛。举个简单的例子
int i,d[100];
d[0]=1;d[1]=1;
for(i=2;i<100;i++)
d[i]=d[i-1]+d[i-2];
printf("%d",d[99]);
上面这个循环d[i]只依赖于前两个数据d[i-1]和d[i-2];
为了节约空间用滚动数组的做法
int d[3];
d[0]=1;d[1]=1;
for(i=2;i<100;i++)
d[i%3]=d[(i-1)%3]+d[(i-2)%3];
printf("%d",d[99%3]);

注意上面的取余运算，我们成功地只保留了需要的最后3个解，数组好象在“滚动”一样，所以叫滚动数组

对于二维也可以用（代码可能不太正确和完善，但是可以理解例子）:
int i,j,d[100][100];
for(i=1;i<100;i++)
for(j=0;j<100;j++)
d[i][j]=d[i-1][j]+d[i][j-1];

上面的d[i][j]只依赖于d[i-1][j],d[i][j-1];
运用滚动数组
int i,,j,d[2][100];
for(i=1;i<100;i++)
for(j=0;j<100;j++)
d[i%2][j]=d[(i-1)%2][j]+d[i%2][j-1];
就是这样

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

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

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