Μετρήστε τρόπους για να φτάσετε στην ένατη σκάλα χρησιμοποιώντας τα βήματα 1, 2 ή 3


Επίπεδο δυσκολίας Εύκολος
Συχνές ερωτήσεις αμαζόνα CodeNation GE Healthcare Microsoft Εργαστήρια Moonfrog PayPal Uber
Συνδυαστικό Δυναμικός προγραμματισμός

Το πρόβλημα «Μετρήστε τρόπους για να φτάσετε στην ένατη σκάλα χρησιμοποιώντας τα βήματα 1, 2 ή 3» δηλώνει ότι στέκεστε στο έδαφος. Τώρα πρέπει να φτάσετε στο τέλος της σκάλας. Πόσοι τρόποι υπάρχουν, λοιπόν, για να φτάσετε στο τέλος, εάν μπορείτε να πηδήσετε μόνο 1, 2 ή 3 βήματα;

Παράδειγμα

Μετρήστε τρόπους για να φτάσετε στην ένατη σκάλα χρησιμοποιώντας τα βήματα 1, 2 ή 3

2
2

εξήγηση

Υπάρχουν 2 τρόποι γιατί είτε φτάνουμε απευθείας στο 2ο βήμα απευθείας από το έδαφος είτε πρώτα φτάνουμε στην 1η σκάλα και μετά προχωράμε μπροστά.

Προσέγγιση

Το πρόβλημα μας ρωτά τον συνολικό διαφορετικό αριθμό τρόπων για να φτάσουμε στο τέλος της σκάλας έτσι ώστε να ξεκινήσουμε από το έδαφος. Επομένως, σκεφτείτε ότι η σκάλα έχει 2 σκαλοπάτια. Έπειτα υπάρχουν 2 πιθανοί τρόποι, είτε πηγαίνετε κατευθείαν στο 2ο βήμα είτε στο πρώτο βήμα στο 1ο βήμα και μετά στο 2ο. Ομοίως, πρέπει να μετρήσουμε τους τρόπους για να φτάσουμε στην ένατη σκάλα χρησιμοποιώντας τα βήματα 1, 2 ή 3.

Μια αφελής προσέγγιση είναι η δημιουργία όλων των πιθανών τρόπων και στη συνέχεια η μέτρησή τους. Αλλά αυτή η προσέγγιση θα είναι χρονοβόρα. Έτσι, για να μειώσουμε την πολυπλοκότητα του χρόνου, πρέπει να σκεφτούμε μερικούς διαφορετικούς τρόπους. Η μέθοδος που συζητήσαμε στην αφελής προσέγγιση είναι μια αναδρομική λύση όπου μπορείτε να ξεκινήσετε από το 0ο βήμα. Στη συνέχεια, σε κάθε αναδρομική κλήση, μεταβείτε στο βήμα i + 1, i + 2 και i + 3. Όταν φτάσετε στο ένατο βήμα αυξήστε τον μετρητή. Με αυτόν τον τρόπο στο τέλος ο μετρητής αποθηκεύει τον αριθμό των τρόπων για να φτάσετε στο ένατο βήμα. Αλλά αυτό το βήμα επαναλαμβάνει τα ίδια προβλήματα ξανά και ξανά. Έτσι, για τη βελτιστοποίηση αυτής της λύσης που χρησιμοποιούμε Δυναμικός προγραμματισμός.

Στη λύση Dynamic Programming, θεωρούμε ότι βρισκόμαστε στο ith βήμα. Στη συνέχεια, ο αριθμός των τρόπων για να φτάσετε στο βήμα είναι από το βήμα i-1, το βήμα i-2 ή το βήμα i-3. Έτσι, επίσημα μιλώντας, τρόποι [i] = τρόποι [i-1] + τρόποι [i-2] + τρόποι [i-3], χρησιμοποιώντας αυτόν τον αναδρομικό τύπο. Θα λύσουμε το πρόβλημά μας.

Κώδικας

Κωδικός C ++ για να μετρήσετε τρόπους για να φτάσετε στο ένατο σκαλοπάτι χρησιμοποιώντας τα βήματα 1, 2 ή 3

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

int main(){
    int n;cin>>n;
    int dp[n+1];
    // base case
    dp[0] = 1;
    for(int i=1;i<=n;i++){
        dp[i] = ((i-1)>=0 ? dp[i-1] : 0) +
                ((i-2)>=0 ? dp[i-2] : 0) +
                ((i-3)>=0 ? dp[i-3] : 0);
    }
    cout<<dp[n];
}
5
13

Κωδικός Java για να μετρήσετε τρόπους για να φτάσετε στο ένατο σκαλοπάτι χρησιμοποιώντας τα βήματα 1, 2 ή 3

import java.util.*;
class Main{
  public static void main(String[] args)
  {
    Scanner sc = new Scanner(System.in);
  int n = sc.nextInt();
    int dp[] = new int[n+1];
    // base case
    dp[0] = 1;
    for(int i=1;i<=n;i++){
        dp[i] = ((i-1)>=0 ? dp[i-1] : 0) +
                ((i-2)>=0 ? dp[i-2] : 0) +
                ((i-3)>=0 ? dp[i-3] : 0);
    }

    System.out.print(dp[n]);
  }
}
5
13

Ανάλυση πολυπλοκότητας

Χρόνος πολυπλοκότητας

ΕΠΙ), γιατί πρέπει να τρέξουμε έναν βρόχο μέχρι το ένατο βήμα. Έτσι, όσον αφορά τον Δυναμικό Προγραμματισμό, είχαμε μία μόνο κατάσταση που κυμαίνεται από 0 έως n και το κόστος μετάβασης είναι O (1). Έτσι, η πολυπλοκότητα του χρόνου είναι γραμμική.

Διαστημική πολυπλοκότητα

ΕΠΙ), αφού πρέπει να δημιουργήσουμε έναν πίνακα DP 1-D. Η διαστημική πολυπλοκότητα της λύσης είναι γραμμική.