70. Climbing Stairs

leetcode easy

#csharp#easy#leetcode#tree

Task

Ты поднимаешься по лестнице. Чтобы добраться до вершины, нужно преодолеть n ступенек.

Каждый раз ты можешь подняться на 1 или 2 ступеньки. Сколькими различными способами ты можешь добраться до вершины?

Пример:

Input: n = 2

Output: 2

Explanation: There are two ways to climb to the top.

1. 1 step + 1 step

2. 2 steps

C# solution

matched/original

public class Solution {
    public int ClimbStairs(int n) {
        return Climb_Stairs(0, n);
    }
    public int Climb_Stairs(int i, int n) {
        if (i > n) {
            return 0;
        }
        if (i == n) {
            return 1;
        }
        return Climb_Stairs(i + 1, n) + Climb_Stairs(i + 2, n);
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int ClimbStairs(int n) {
        return Climb_Stairs(0, n);
    }
    public int Climb_Stairs(int i, int n) {
        if (i > n) {
            return 0;
        }
        if (i == n) {
            return 1;
        }
        return Climb_Stairs(i + 1, n) + Climb_Stairs(i + 2, n);
    }
}

Java solution

matched/original

public class Solution {
    public int climbStairs(int n) {
        return climb_Stairs(0, n);
    }

    public int climb_Stairs(int i, int n) {
        if (i > n) {
            return 0;
        }
        if (i == n) {
            return 1;
        }
        return climb_Stairs(i + 1, n) + climb_Stairs(i + 2, n);
    }
}

JavaScript solution

matched/original

var climbStairs = function (n) {
    return climb_Stairs(0, n);
};
var climb_Stairs = function (i, n) {
    if (i > n) {
        return 0;
    }
    if (i == n) {
        return 1;
    }
    return climb_Stairs(i + 1, n) + climb_Stairs(i + 2, n);
};

Python solution

matched/original

class Solution:
    def climbStairs(self, n: int) -> int:
        return self.climb_Stairs(0, n)

    def climb_Stairs(self, i: int, n: int) -> int:
        if i > n:
            return 0
        if i == n:
            return 1
        return self.climb_Stairs(i + 1, n) + self.climb_Stairs(i + 2, n)

Go solution

matched/original

func climbStairs(n int) int {
    return climb_Stairs(0, n)
}

func climb_Stairs(i int, n int) int {
    if i > n {
        return 0
    }
    if i == n {
        return 1
    }
    return climb_Stairs(i+1, n) + climb_Stairs(i+2, n)
}

Explanation

Algorithm

1️⃣

В этом методе грубой силы мы рассматриваем все возможные комбинации шагов, то есть 1 и 2, на каждом шаге.

2️⃣

На каждом шаге мы вызываем функцию climbStairs для шага 1 и шага 2, и возвращаем сумму возвращаемых значений обеих функций.

3️⃣

Формула вызова функции: climbStairs(i, n) = climbStairs(i+1, n) + climbStairs(i+2, n), где i определяет текущий шаг, а n — целевой шаг.

😎