描述
一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法(先后次序不同算不同的结果)。
思路
跳 1 个台阶,有一种跳法;跳 2 个台阶,有两种跳法;跳 3 个台阶,有三种跳法;跳 4 个台阶,有五种跳法;跳 5 个台阶,有八种跳法......
不知道大家发现啥规律没,从第三个台阶开始,每个台阶的跳法数量就是前一个和前两个台阶的跳法总和。
其实这个也很好理解,咱们想想,我要跳到一个台阶其实只有两条路,一个是从前一个跳过来;另一个就是从前两个台阶跳过来。那么该台阶的跳法自然就是前两个台阶的跳法总和了。
看看是不是这个道理。有了思路了这道题就好写了。
AC代码
方法一
public int jumpFloor(int target) { if (target == 1 || target == 2) { return target; } // dp 数组,用来存储结果 int[] dp = new int[target]; // 第一个台阶是 1 dp[0] = 1; // 第二个台阶时 2 dp[1] = 2; for (int i = 2; i < target; i ++) { // 通过公式推导 dp[i] = dp[i - 1] + dp[i - 2]; } // 返回第 target 个台阶的跳法 return dp[target - 1]; }
时间复杂度:O(n),n 为台阶数,每个台阶要遍历一遍
空间复杂度:O(n),n 为台阶数,每个台阶对应跳法数量要存储起来。
方法二
这个其实每次还要记住前两个台阶的数量就可以,那么咱们就不需要用存储
所有的台阶的跳法数量,只需要存储前两个就可以。
public int jumpFloor(int target) { if (target == 1 || target == 2) { return target; } // 第一个台阶是 1 int dp_1 = 1; // 第二个台阶是 2 int dp_2 = 2; // 开始遍历 for (int i = 3; i <= target; i ++) { // 获取前两个台阶总和 int temp = dp_1 + dp_2; // 迭代 dp_1 = dp_2; dp_2 = temp; } return dp_2; }
时间复杂度:O(n),n 为台阶数,每个台阶要遍历一遍
空间复杂度:O(1)
最后
这道题是最基础的动态规划算法题,这道题能让咱们入门动态规划,之后我也会由浅入深的继续和大家探索动态规划。让其不太神秘。
大家可以去 【牛客网-题库-在线编程】去练习一下。
可以去微信搜索:【蘑菇睡不着】交个朋友~
也可以扫描下方二维码。