题目描述
一只青蛙一次可以跳上1级台阶,也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
示例1
输入
复制
3
返回值
复制
4
思路:每次跳台阶都可以从任一台阶跳过来。所以每个台阶的跳法数目等于之前从各台阶跳过来的次数综合
即数组的第i+1个元素,是前i个元素的总和。其中第一个元素是1.直接进行动态规划即可。

public class Solution {
    //动态规划   12ms 9656KB
    public int JumpFloorII(int target) {
        int[] ans=new int[target];
        int tag=1;
        for(int i=0;i<target;i++){
            ans[i]=tag;
            tag+=ans[i];
        }
        return ans[target-1];
    }
}