题解 | #跳台阶#

1.思路

秒懂【爬楼梯】！动态规划一步步拆解。

本题的关键是套用动态规划的模板，对问题进行拆解。

具体思路是：

如果文字描述的不太清楚，你可以参考视频的详细讲解：B站@好易学数据结构

2.代码

2.1 Python代码

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param number int整型
# @return int整型
#
class Solution:
    def jumpFloor(self, number: int) -> int:
        # write code here
        if number == 1:
            return 1
        # 1. 定义状态.i: 第i个台阶； dp[i]: 跳到第i个台阶的跳法
        dp = [0] * (number + 1)
        # 2. 初始化边界条件：    dp[1] = 1，即第一个台阶只有1种跳法；dp[2] = 2，即第二个台阶有2种跳法；
        dp[1] = 1
        dp[2] = 2
        # 3. 确定递推公式： dp[i] = dp[i - 1] + dp[i - 2]
        for i in range(3, number + 1):
            # 到第i个台阶有2种方法：从第 i-1跳上来，或者从第 i-2跳上来
            dp[i] = dp[i - 1] + dp[i - 2]
        # 4.输出结果
        return dp[number]

2.2 Java代码

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param number int整型
     * @return int整型
     */
    public int jumpFloor (int number) {
        // write code here
        if (number == 1) {
            return 1;
        }
        //1.定义状态.   i:第i个台阶； dp[i]:跳到第i个台阶的跳法
        int[] dp = new int[number + 1];
        //2.初始化边界条件：    dp[1]=1，即第一个台阶只有1种跳法；dp[2]=2，即第二个台阶有2种跳法；
        dp[1] = 1;
        dp[2] = 2;
        //3.确定递推公式： dp[i]=dp[i-1]+dp[i-2]
        for (int i = 3; i <= number; i++) {
            //到第i个台阶有2种方法：从第 i-1跳上来，或者从第 i-2跳上来
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        //4.输出结果
        return dp[number];
    }
}

2.3 Go代码

package main

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param number int整型
 * @return int整型
 */
func jumpFloor(number int) int {
	// write code here
	if number == 1 {
		return 1
	}
	//1.定义状态.	i:第i个台阶； dp[i]:跳到第i个台阶的跳法
	dp := make([]int, number+1)
	//2.初始化边界条件：	dp[1]=1，即第一个台阶只有1种跳法；dp[2]=2，即第二个台阶有2种跳法；
	dp[1] = 1
	dp[2] = 2
	//3.确定递推公式： dp[i]=dp[i-1]+dp[i-2]
	for i := 3; i <= number; i++ {
		//到第i个台阶有2种方法：从第 i-1跳上来，或者从第 i-2跳上来
		dp[i] = dp[i-1] + dp[i-2]
	}
	//4.输出结果
	return dp[number]
}

如果上面的代码理解的不是很清楚，你可以参考视频的详细讲解：B站@好易学数据结构