题目描述

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

答案

public class Solution {
    public int JumpFloorII(int target) {
        int[] dp =new int[target+1];
        dp[0] = 1;
        for(int i=1;i<=target;i++){
            dp[i] = 0;
            for(int y=0;y<i;y++){
                dp[i]+=dp[y];
            }
        }
        return dp[target];
    }
}

解析

跳全部台阶:1---f(0)
跳第一级台阶:1---f(1)
跳第二级台阶:2---f(2)

跳第三级台阶:
1. 先跳1级,剩下2级台阶是f(3-1)
2. 先跳2级,剩下1级台阶是f(3-2)
3. 直接跳3级,所以是f(3-3)

引申:f(n) = f(n-1)+f(n-2)+...+f(0)

注意:先跳1再跳2,和先跳2再跳1不会有重复吗?
答:不会,先跳1再跳2,是在跳1已经确定的基础上决定的,先跳2再跳1也是在2已经确定的基础上再跳1


醉后不知天在水,满船清梦压星河