Addım 1, 2 və ya 3-dən istifadə edərək üçüncü pilləyə çatmağın yollarını sayın

Problem "1, 2 və ya 3 addımını istifadə edərək üçüncü pilləyə çatmağın yollarını sayın" problemi yerdə dayandığınızı bildirir. İndi nərdivanın sonuna çatmalısınız. Bəs yalnız 1, 2 və ya 3 addım atlaya bilsən sona çatmağın neçə yolu var?

misal

Pin

2

2

Izahat

2 yol var, çünki ya birbaşa birbaşa yerdən 2-ci pilləyə çatırıq, ya da əvvəlcə 1-ci pilləyə çatırıq, sonra irəliləyirik.

Yanaşma

Problem bizə nərdivanın sonuna çatmağın yerdən başlamağımız üçün ümumi fərqli sayını tələb edir. Beləliklə, pilləkənlərin 2 pilləli olduğunu düşünün. Sonra 2 mümkün yol var, ya birbaşa 2-ci pilləyə, ya da ilk pilləyə 1-ci pilləyə, sonra da 2-yə addım atın. Eynilə, 1-ci, 2-ci və ya 3-cü pillələrdən istifadə edərək üçüncü pilləyə çatmağın yollarını saymalıyıq.

Sadəlövh yanaşma bütün mümkün yolları yaratmaq və sonra saymaqdır. Ancaq bu yanaşma çox vaxt aparacaq. Beləliklə, zamanın mürəkkəbliyini azaltmaq üçün müxtəlif yolları düşünməliyik. Sadəlövh yanaşmada müzakirə etdiyimiz metod a rekursiv 0 addımdan başlaya biləcəyiniz həll. Sonra hər bir rekursiv çağırışda i + 1, i + 2 və i + 3 addımlarına keçin. N addıma çatdıqda sayğacı artırın. Sonda sayğac sayca ninci pilləyə çatmağın sayını saxlayır. Ancaq bu addım eyni problemləri yenidən təkrarlayır. Beləliklə, bu həlli optimallaşdırmaq üçün istifadə edirik Dinamik proqramlaşdırma.

Dinamik Proqramlaşdırma həllində ith addımda olduğumuzu düşünürük. Sonra ith addıma çatmağın yolu i-1 pillədən, i-2 pillədən və ya i-3 pillədəndir. Yəni rəsmi olaraq danışsaq, yollar [i] = yollar [i-1] + yollar [i-2] + yollar [i-3], bu rekursiv düsturdan istifadə edərək. Problemimizi həll edəcəyik.

Kodu

Adım 1, 2 və ya 3-dən istifadə edərək üçüncü pilləyə çatmağın yollarını saymaq üçün C ++ kodu

#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

Addım 1, 2 və ya 3-dən istifadə edərək üçüncü pilləyə çatmağın yollarını saymaq üçün Java kodu

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

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi

O (N), çünki ikinci addıma qədər bir döngə aparmalıyıq. Deməli, Dinamik Proqramlaşdırma baxımından 0 ilə n arasında dəyişən tək bir vəziyyətimiz var və keçid dəyəri O (1) -dir. Beləliklə, zamanın mürəkkəbliyi doğrudur.

Kosmik Mürəkkəblik

O (N), çünki 1 ölçülü DP seriyası yaratmalıyıq. Solüsyonun kosmik mürəkkəbliyi xətti.