Wchodzenie po schodach

Pytania do rozmowy kwalifikacyjnej na temat projektowania systemu może być tak nieograniczona, że ​​trudno jest określić właściwy sposób przygotowania. Teraz jestem w stanie złamać rundy projektowe Amazon, Microsoft i Adobe po zakupie ta książka. Codziennie poprawiaj jeden pytanie projektowe i obiecuję, że możesz złamać cały projekt.

Problem Statement

Problem „Wchodzenie po schodach” mówi, że masz klatkę schodową z n schodami. Jednocześnie możesz wspiąć się po jednym lub dwóch schodach. Ile jest sposobów, aby dostać się na szczyt schodów?

Przykład

3

3

Wyjaśnienie

Na szczyt można wejść na trzy sposoby.

1. 1 stopień + 1 stopień + 1 stopień

2. 1 stopień + 2 stopnie

3. 2 stopnie + 1 krok

szpilka

Obraz przedstawia sposoby poruszania się.

Więc nasza odpowiedź to 3.

Podejście rekurencyjne

Możemy zaobserwować, że liczba dróg dotarcia do i-tego stopnia jest sumą liczby dróg dotarcia do (i-1) schodów i liczby dróg do osiągnięcia (i-2) schodów. Staje się więc nasze równanie rekurencyjne

ways(n) = ways(n-1) + ways(n-2)

Kod

Kod C ++ do wspinania się po schodach

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

// A recursive function used by countWays 
int countWaysUtil(int n, int m) 
{ 
  if (n <= 1) 
  { 
    return n; 
  } 
  
  int res = 0; 
  for(int i = 1; i <= m && i <= n; i++) 
  { 
  res += countWaysUtil(n - i, m); 
  } 
  return res; 
} 

// Returns number of ways to reach s'th stair 
int countWays(int s, int m) 
{ 
  return countWaysUtil(s + 1, m); 
} 

// Driver code 
int main() 
{ 
  int s = 4, m = 2; 
  cout << "Nuber of ways = " << countWays(s, m); 

  return 0; 
}

5

Kod Java do wspinania się po schodach

class stairs { 
  // A recursive function used by countWays 
  static int countWaysUtil(int n, int m) 
  { 
    if (n <= 1) 
      return n; 
    int res = 0; 
    for (int i = 1; i <= m && i <= n; i++) 
      res += countWaysUtil(n - i, m); 
    return res; 
  } 

  // Returns number of ways to reach s'th stair 
  static int countWays(int s, int m) 
  { 
    return countWaysUtil(s + 1, m); 
  } 

  /* Driver program to test above function */
  public static void main(String args[]) 
  { 
    int s = 4, m = 2; 
    System.out.println("Number of ways = "
            + countWays(s, m)); 
  } 
}

5

Analiza złożoności

Złożoność czasowa

O (2 ^ n), ponieważ w podejściu rekurencyjnym dla każdego stopnia mamy dwie możliwości: wchodzić po jednym stopniu na raz lub wchodzić po dwóch schodach naraz. Ponieważ sprawdzamy wszystkie możliwe przypadki, więc dla każdego schodów mamy 2 opcje i mamy łącznie n schodów, więc złożoność czasowa staje się złożona O (2 ^ n)

Złożoność przestrzeni

Na) ponieważ kompilator wymaga miejsca, aby użyć rekursji. Rekursja wymaga również stosu, a tym samym przechowywania, co tworzy tę przestrzeń O (n), ponieważ rekursja będzie prawie n głęboka.

Dynamiczne podejście do programowania

Podejście rekurencyjne obejmuje wielokrotne przeliczanie tych samych wartości. W tym celu używamy zapamiętywania, a kiedy obliczamy go dla jakiegoś wejścia, przechowujemy go w pliku zapamiętywanie stół. Kiedy potrzebujemy go później, nie obliczamy go ponownie i bezpośrednio używamy jego wartości z tabeli. Utrzymujemy tabelę sposobów [], gdzie sposoby [i] przechowują liczbę dróg do osiągnięcia i-tego stopnia. Zatem sposoby [n-1] to nasza odpowiedź.

Kod

Kod C ++ do wspinania się po schodach

#include <stdio.h> 

// A recursive function used by countWays 
int countWaysUtil(int n, int m) 
{ 
  int res[n]; 
  res[0] = 1; 
  res[1] = 1; 
  for (int i = 2; i < n; i++) { 
    res[i] = 0; 
    for (int j = 1; j <= m && j <= i; j++) 
      res[i] += res[i - j]; 
  } 
  return res[n - 1]; 
} 

// Returns number of ways to reach s'th stair 
int countWays(int s, int m) 
{ 
  return countWaysUtil(s + 1, m); 
} 

// Driver program to test above functions 
int main() 
{ 
  int s = 4, m = 2; 
  printf("Number of ways = %d", countWays(s, m)); 
  return 0; 
} 

5

Kod Java do wspinania się po schodach

// Java program to count number of ways 
// to reach n't stair when a person 
// can climb 1, 2, ..m stairs at a time 

class stairs { 
  // A recursive function used by countWays 
  static int countWaysUtil(int n, int m) 
  { 
    int res[] = new int[n]; 
    res[0] = 1; 
    res[1] = 1; 
    for (int i = 2; i < n; i++) { 
      res[i] = 0; 
      for (int j = 1; j <= m && j <= i; j++) 
        res[i] += res[i - j]; 
    } 
    return res[n - 1]; 
  } 

  // Returns number of ways to reach s'th stair 
  static int countWays(int s, int m) 
  { 
    return countWaysUtil(s + 1, m); 
  } 

  // Driver method 
  public static void main(String[] args) 
  { 
    int s = 4, m = 2; 
    System.out.println("Number of ways = "
            + countWays(s, m)); 
  } 
}

5

Analiza złożoności

Złożoność czasowa

O (m * n) tutaj m to liczba dróg, która dla tego problemu wynosi 2, an to liczba schodów.

Złożoność przestrzeni

Na) ponieważ używamy tablicy o rozmiarze n, w której każda pozycja przechowuje liczbę sposobów dotarcia do tej pozycji.