多阶梯问题求解

唉，回来看看股票有跌了啊！杯具

比较有意思的一个问题，一个人能够一步上n个阶梯，如当其步长为2，则有1+1， 2两种， 3则有1+1+1，1+2，2+1， 3 四种

当m级阶梯上的方法有多少种？

/**
 * 
 */
/**
 * @author jie.xiang
 * 
 */
public class StairsCounter {
	private int stepLen = 2;
	private BigNumberCounter counter = new BigNumberCounter();
	/**
	 * @param stairsNum
	 * @param stepLen
	 */
	public StairsCounter(int stepLen) {
		super();
		this.stepLen = stepLen;
	}
	public String getStepWays(int n) {
		if (n <= stepLen) {
			if (n <= 1) {
				return "1";
			} else if (n == 2) {
				return "2";
			} else {
				String stempLengthWay = "1";
				for (int i = n - 1; i >= 1; i--) {
					stempLengthWay = counter.addNumbers(stempLengthWay,
							getStepWays(i));
				}
				return stempLengthWay;
			}
		} else {
			String result = "0";
			for (int i = stepLen; i >= 1; i--) {
				result = counter.addNumbers(result, getStepWays(n - i));
			}
			return result;
		}
	}
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int number = 10;
		StairsCounter counter = new StairsCounter(8);
		System.out.println("The " + number + " stairs is:"
				+ counter.getStepWays(number));
	}
}

其中BigNumberCounter请参见：大数运算

结果为：The 10 stairs is:509

这个递归只是为了逻辑简单，如果为了效率的话，应该将其改为循环，因为递归是一个进出栈的过程，相当消耗时间与空间。

呵呵，时间问题，就不在这里再写了