9.剑指offer-变态跳台阶*

题干

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

我的思路

还是按递归的思路去做，但是用循环的写法提升执行效率。
推导出来公式：f(n) = f(n-1)+f(n-2)+…f(1)+1;
1的意思是从0直接跳到n阶，一步到位。

我的代码

import java.util.*;
public class Solution {
    public int JumpFloorII(int target) {
        if (target <= 2) {
            return target;
        }
        int[] dp = new int[target + 1]; //防止数组下标越界，长度是+1
        dp[0] = 0; //从 0 跳到 0 为 0 种，因为 n = 0，没法跳
        dp[1] = 1;//因为不是递归所以得赋值，没办法通过递归赋值
        dp[2] = 2;
        for (int i = 3; i <= target; i++) {
            for (int j = i - 1; j >= 1; j--) {
                dp[i] += dp[j]; //第 n 个状态是由前 n - 1 种状态推导出来，就是累加！
            }
            dp[i]+=1;
        }
        return dp[target];
    }
}

大佬解析

import java.util.*;
public class Solution {
    public int JumpFloorII(int target) {
        if (target <= 2) {
            return target;
        }
        int[] dp = new int[target + 1];
        Arrays.fill(dp, 1); //初始化每一种都可以直接从 0 跳到 n
        dp[0] = 0; //从 0 跳到 0 为 0 种，因为 n = 0，没法跳
        for (int i = 2; i <= target; i++) {
            for (int j = i - 1; j >= 1; j--) {
                dp[i] += dp[j]; //第 n 个状态是由前 n - 1 种状态推导出来，就是累加！
            }
        }
        return dp[target];
    }
}

总结

1.用循环代替递归的时候，记得数组里的每一个位置都是需要你去赋值的，而不是让递归给你迭代出来。
2. int[] dp = new int[target + 1]; //防止数组下标越界，初始化的时候可以这么写。