剑指offer（九）变态跳台阶

点击进入 牛客网题库：变态跳台阶

题目描述

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

方法一 迭代的方式

public class Solution {
    /**
    * f(n) : f(n-1) + f(n -2)+...+f(0) + 1 
    *
    * f(0) : 0
    * f(1) : 1
    * f(2) : 1 + 1
    * f(3) : 1,1,1 1,2 2,1 3
    
    *
    */
    public int JumpFloorII(int target) {
       if(target == 0) {
           return 0;
       }  
        
       if(target == 1) {
           return 1;
       }
       
       int dp[] = new int[target + 1];
       dp[0] = 0;
       dp[1] = 1;
       
        for(int i = 2; i <= target; i++) {
            int tmp = 0;
            for(int j = 0; j < i; j++) {
                tmp+=dp[j];
            }
            dp[i] = tmp + 1;
        }
        
      return dp[target];
        
    }
}