0057.爬楼梯.md

57. 爬楼梯

题目链接

C++

#include <iostream>
#include <cmath>
#include <vector>
using namespace std;
int main() {
    int n, m;
    while (cin >> n >> m) {
        vector<int> dp(n + 1, 0);
        dp[0] = 1;
        for (int i = 1; i <= n; i++) { // 遍历物品
            for (int j = 1; j <= m; j++) { // 遍历背包
                if (i - j >= 0) dp[i] += dp[i - j];
            }
        }
        cout << dp[n] << endl;
    }
}

Java

import java.util.Arrays;
import java.util.Scanner;

public class Main {

    public static int climbStairs(int n, int m) {
        int[] dp = new int[n + 1];
        Arrays.fill(dp, 0);
        dp[0] = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (i - j >= 0) {
                    dp[i] += dp[i - j];
                }
            }
        }
        return dp[n];
    }
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        System.out.println(climbStairs(n, m));
    }
}

Python

n,m = input().split(' ')  
n = int(n)
m = int(m)
dp = [0] * (n + 1)
dp[0] = 1
for i in range(1,n+1):
    for j in range(1,m+1):
        if (i - j >= 0):
            dp[i] += dp[i - j]
            
print(dp[n])
            

JS

// 引入readline模块，并定义rl对象的输入输出流接口
const readline = require('readline');
const rl = readline.createInterface({
    input:process.stdin,
    output:process.stdout
})
// rl对象监听IO行输入事件，每行只有一个<string>参数
rl.on('line', (s) => {
    let [n,m] = s.split(' ')
    // console.log("input", n, m)
    console.log(climbNStairsByM(n,m))
})

// 爬楼梯
function climbNStairsByM(n, m){
    // 初始化dp数组
    const dp = [];
    dp[0] = 1;
    dp[1] = 1;

    for(let i = 2; i <= n; i++ ) {

        //状态转移方程
        dp[i] = 0;
        for(let j = 1; j <= m; j++) {
            if (j > i) break; // i-j为负数后就不用算了
            dp[i] += dp[i - j];
        }

    }
    return dp[n];
}

Go

package main
import (
	"fmt"
)

func main(){
    var n,m int
    fmt.Scanf("%d %d",&n,&m)
    var dp = make([]int,n + 1)
    dp[0] = 1
    for  i := 1;i <= n;i++ {
        for j := 1;j <= m;j++ {
            if i - j >= 0 {
                dp[i] += dp[i - j]
            }
        }
    }
    fmt.Println(dp[n])
    
}

C