题目描述:
小明很讨厌爬楼梯。每次回家的时候，小明都要爬过那长长的(至少对刚刚6岁的小明来说)n阶楼梯(1 < n <= 500)，回到温暖的家。经过长时间的总结，小明发现一步上ki阶楼梯(0 < i <= s, 0 < ki <= 30)的时候，会比较省力气，这样的ki一共有s(1 <= s <= 10)种。小明当然想省点力气好回家做作业。小明很想知道自己要从一楼回到家一共有多少种省力的爬法。
输入:
第1行：两个整数n s
第2行：s个整数k1 k2 … ks

输出:
第1行：一个整数m，省力的上楼回家的方法数。(保证m < 2^31)
样例输入:
5 2
2 3

样例输出:
2

样例解释:
每次上2阶或每次上3阶会比较省力。要上5阶的楼梯，有2种上法：先上2阶，再上3阶和先上3阶，再上2阶。其他的方法都不能准确地上到第5层台阶(比如上3次2阶，虽然能上到第6阶，但超过了5阶)，所以不是一个解。

有没有高人阿。
既要组合又要排列阿。
确实比较难。

那如果输入是
5，3
1，2，3
输出是多少种呢？
是说将全部的ki都要用，还是说随便用不用只要达到目的地？

[此贴子已经被作者于2006-5-25 16:53:00编辑过]

s不可能是2
s应该是3了
因为s等于ki的个数。
我理解可以有不用的。要不就简单了阿。

为什么ki可以是30？小孩可以一步上30？神也不行啊~！

用穷举吧
就是一个一个试
关键是最后一步，I++（0~I）要是走多了
就算了说明前几个步法够了
然后让它后退一下（也就是还剩够两步的台阶）
然后再一个一个试
然后再后退
至到最后一个
用FOR循环

晕，不是吧，每人会做？

#include<iostream>
using namespace std;
int main()
{
int n,s,j,i,sta[10],ans[510];
while(cin>>n>>s)
{
for(i=0;i<s;++i)
cin>>sta[i];
memset(ans,0,sizeof(ans));
ans[0]=1;
for(i=1;i<=n;++i)
{
for(j=0;j<s;j++)
{
if(i>=sta[j] && ans[i-sta[j]]>0)
ans[i]+=ans[i-sta[j]];
}
}
cout<<ans[n]<<endl;

}
}

我这个上面的算法还有一个小问题，
不能定义成int否则有可能越界，要定义成unsigned long 型的。

你想过你输入的数字可能有重复的没？