爬楼梯

[编程题]爬楼梯

热度指数：18370 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

在你面前有一个n阶的楼梯，你一步只能上1阶或2阶。
请问计算出你可以采用多少种不同的方式爬完这个楼梯。

输入描述:

一个正整数n(n<=100)，表示这个楼梯一共有多少阶

输出描述:

一个正整数，表示有多少种不同的方式爬完这个楼梯

示例1

输入

输出

算法知识视频讲解

JavaScript Node

牛客944083017号

这道题不考虑大数相加的话是这样的思路，和斐波拉一样

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

void async function () {
    // Write your code here
    while(line = await readline()){
        let num = Number(line)
        let dp = new Array(num+1).fill(0)
        dp[1] = 1
        dp[2] = 2
        for(let i = 3; i <= num; i++) {
            dp[i] = dp[i-1] + dp[i-2]
        }
        console.log(dp[num])
    }
}()

但是这道题，必须得考虑大数相加

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

void async function () {
    // Write your code here
    while(line = await readline()){
        let num = Number(line)
        let dp = new Array(num+1).fill(0)
        dp[1] = 1
        dp[2] = 2
        for(let i = 3; i <= num; i++) {
            dp[i] = numAdd(dp[i-1].toString(), dp[i-2].toString())
        }
        console.log(dp[num])
    }
    /**
     * 这个函数是用来进行大数相加的，可以反复阅读一下
     */
    function numAdd(first, second) {
        // 取两个数字的最大长度
        let maxLength = Math.max(first.length, second.length);
        // 用 0 去补齐长度
        first = first.padStart(maxLength , 0);
        second = second.padStart(maxLength , 0); 
        // 定义加法过程中需要用到的变量
        let temp = 0;
        let carry = 0;   // "进位"
        let sum = "";
        for(let i = maxLength-1; i >= 0; i--){
            temp = parseInt(first[i]) + parseInt(second[i]) + carry;
            carry = Math.floor(temp / 10);
            sum = temp % 10 + sum;
        }
        if(carry == 1){
            sum = "1" + sum;
        }
        return sum;
    }
}()

发表于 2023-04-16 21:01:07 回复(0)