首页 > 试题广场 >

序号6

[编程题]序号6
  • 热度指数：2036 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
段誉身具凌波微波，动无常则，若危若安，一次能走一级台阶或者两级台阶，他要爬一段30级的山路，问有多少种走法？分析如何计算，然后编程解答。
进阶问题：当他轻功熟练度提升，一次最多可以走三级，那就结果有什么变化？后来走火入魔了，不能走一级，只能走二或三级，又有什么变化？

输入描述:
输入一个数n（1<=n<=30），代表段誉要爬一段n级的山路。


输出描述:
输出三个整数a,b,c（以空格相间）。其中a为段誉一次能走一级或两级台阶的走法；b为段誉一次能走一级、二级或三级台阶的走法；c为段誉一次能走二级或三级台阶的走法。
示例1

输入

3

输出

3 4 1
算法知识视频讲解
添加回答
Java
霏奥其头像 霏奥其
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int stairs = in.nextInt();
        int res1 = climbStairs1(stairs);
        int res2 = climbStairs2(stairs);
        int res3 = climbStairs3(stairs);
        System.out.printf("%d %d %d", res1, res2, res3);
    }

    // 将爬楼梯问题转化为完全背包
    // 背包为楼梯数，物品为段誉每次可以选择的走法
    public static int climbStairs1(int target) {
        int[] dp = new int[target+1];
        int[] choose = {1, 2};
        dp[0] = 1;
        // 求排列，先遍历背包，再遍历物品
        // 正序遍历
        for (int i=0; i<=target; i++) {
            for (int j=0; j<choose.length; j++) {
                if (i >= choose[j]) {
                    dp[i] += dp[i - choose[j]];
                }
            }
        }
        return dp[target];
    }

    public static int climbStairs2(int target) {
        int[] dp = new int[target+1];
        int[] choose = {1, 2, 3};
        // dp[0] 无意义，为了满足计算公式设为1
        dp[0] = 1;
        for (int i=0; i<=target; i++) {
            for (int j=0; j<choose.length; j++) {
                if (i >= choose[j]) {
                    dp[i] += dp[i - choose[j]];
                }
            }
        }
        return dp[target];
    }

    public static int climbStairs3(int target) {
        int[] dp = new int[target+1];
        int[] choose = {2, 3};
        dp[0] = 1;
        for (int i=0; i<=target; i++) {
            for (int j=0; j<choose.length; j++) {
                if (i >= choose[j]) {
                    dp[i] += dp[i - choose[j]];
                }
            }
        }
        return dp[target];
    }
}
发表于 2023-04-05 15:32:08 回复(0)
提交观点

问题信息

4399游戏 游戏研发工程师
来自：2020校招4399游...
上传者：小小
难度：
1条回答 5724浏览

热门推荐

通过挑战的用户

相关试题

序号6

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号