算法练习-贪心问题

问题：

一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

分析：

　　（1）、当想要到达n阶时，青蛙的前一个状态可能停留在1~n-1的任意一个范围内。

　　（2）、同理，可以将问题逐步分割。

　　（3）、到达阶梯1和阶梯2的值时确定的，根据此可以搜索完所有状态。

code：

public int JumpFloorII(int target) {
        if(target==0) {
            return 0;                                                                                         
        }else if(target==1) {
            return 1;
        }else {
            int step[] = new int[target+1];
            step[0]=1;//从0位置起跳。
            step[1]=1;
            for(int i=2;i<=target;i++) {
                for(int j=i-1;j>=0;j--) {
                    step[i]+=step[j];
                }
            }
            return step[target];
        }
    }