Airthmetic_backdate_Upstairs

由于回溯法比较常用跟重要，所以就再来练习一个，也是比较经典的爬楼梯的问题

问题描述 : 爬楼梯，每次只能上1层或者2层，现在问有多少种爬法？假设楼梯有20层

思想 ：主要就是回溯的思想，列举出所有的解空间树，从1 或者 2开始，往下，如果总共有加起来刚刚好等于20，就count++，然后return了，返回到上一个父节点，看例外一个节点满足不，如果是总共加起来大于20了，就直接return，如果还没有20，那就继续走下去，再一次判断是走一层还是两层，也就是每次走都要判断是走一层还是走两层，很明显，这是一个递归的思想，其实回溯的主要就是一种递归的感觉。

当然对于这道题还有一个技巧就是将每次的层数就是1或者2放到一个数组中去，这样主要是好遍历，便于观察和记录，然后最后就变成求一个数组，什么时候全部元素相加为20，要求每一个元素只能是1或者2

上代码

package thinking;

/*
 * 上楼梯 ： 每次只能上一步和两步，现在如果20层，问现在有多少种走法
 * 
 * 思想都是回溯的思想
 * */

public class Upstairs_backDate {
    int Max_Stairs = 20;
    int[] Steps = new int[Max_Stairs];
    int Count=0;
    /*
     * @param
     * footstep : 当前要走的步数 1或者 2
     * count : 总共走了多少层
     * steps : 第几步
     * */
    public void UpStairs(int footstep, int count, int steps){
        // 当已经刚刚走完了
        if(footstep + count == Max_Stairs){
            Steps[steps] = footstep;
            Count++;
            count+=footstep;
            for(int i=0; i<steps; ++i){
                System.out.print(Steps[i]); // 走的情况
            }
            System.out.println();
            return;
        }
        
        // 若出现大于的情况
        if(footstep + count > Max_Stairs){
            return;
        }
        
        // 继续走
        Steps[steps] = footstep;
        count += footstep;
        steps++;
        
        for(int i=1; i<=2; ++i){
            UpStairs(i, count, steps);
        }
    }
    
    public void UpstairsStart(){
        UpStairs(1, 0, 0);
        UpStairs(2, 0, 0);
    }
    
    public static void main(String[] args) {
        Upstairs_backDate up = new Upstairs_backDate();
        up.UpstairsStart();
        System.out.println(up.Count);
    }
}