[数据结构与算法]【动态规划】【打卡114天】《剑指Offer》2刷：变态跳台阶：JZ71 跳台阶扩展问题

1、题目描述

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

2、算法分析

一只青蛙一次可以跳1级，2级，...n级的台阶。求跳n阶台阶共有多少种跳法。

像这种计数的题目；比如多少种方式，多少种方法。都可以使用dp方法解题。

之前做过一道基础的题目，但是只能是跳1级或者2级。

也就是看最后一步。f[i] = f[i-1] + f[i-2];

本题：

青蛙可以跳1级，2级，...n级的台阶，所以分为5步走：

①确定dp数组以及下标含义

dp[i]:第i级台阶有多少种跳法

②确定递推公式

当target = 1，dp[1] = 1

当target = 2，dp[2] = 1+dp[1]；0到1到2；0直接跳到2；

当target = 3，dp[3] = dp[2] + 1 ；dp[2]的次数再跳1步骤就可以跳到dp[3]，最后 + 1是从0级台阶直接跳到第3级。

f[n] = f[n-1] + f[n-2] + ... + f[0]

③初始化

注意，这儿应该先判断target是否<2

  dp[1] = 1;
  dp[2] = 2;

④确定遍历顺序

当然是顺序遍历

3、代码实现

import java.util.*;
public class Solution {
    public int jumpFloorII(int target) {
        // 定义dp数组：dp[i]：i级台阶可以有多少种跳法
        int[] dp = new int[target+1];
        if(target <=2){
            return target;
        }
        // 初始化
        dp[1] = 1;
        dp[2] = 2;
        // 从3开始
        for(int i = 3;i <= target;i++){
            for(int j = 1;j < i;j++){
                // f[n] = f[n-1] + f[n-2] + ... + f[0]
                dp[i] += dp[j];
            }
            // 最后加的是：从0级跳到n级
            dp[i] += 1;
        }
        return dp[target];
    }
}