1-ші, 2-ші немесе 3-ші қадамдар арқылы баспалдаққа жету жолдарын санаңыз  


Күрделілік дәрежесі оңай
Жиі кіреді Amazon CodeNation GE Healthcare Microsoft Moonfrog зертханалары PayPal қиятын
Комбинаторлық Динамикалық бағдарламалау

«1-ші, 2-ші немесе 3-ші қадамдарды қолданып, үшінші баспалдаққа жету жолдарын санау» мәселесі сіздің жерде тұрғаныңызды білдіреді. Енді сіз баспалдақтың соңына жетуіңіз керек. Сонымен, сіз тек 1, 2 немесе 3 қадамнан секіре алсаңыз, соңына жетудің қанша жолы бар?

мысал  

1-ші, 2-ші немесе 3-ші қадамдар арқылы баспалдаққа жету жолдарын санаңызтүйреуіш

2
2

Түсіндіру

Екі жол бар, өйткені біз 2-ші сатыға тікелей жерден жетеміз немесе алдымен 2-ші баспалдаққа жетеміз, содан кейін алға жылжимыз.

жақындау  

Мәселе бізден баспалдақтың соңына жету үшін жерден бастауға болатын әр түрлі тәсілдерді сұрайды. Сондықтан баспалдақтың 2 сатысы бар екенін қарастырыңыз. Содан кейін мүмкін болатын 2 әдіс бар, немесе сіз тікелей 2-ші қадамға немесе бірінші қадамға 1-ші қадамға, содан кейін 2-ші қадамға асығыңыз. Сол сияқты, біз 1-ші, 2-ші немесе 3-ші қадамдарды қолданып, n-ші баспалдаққа жету жолдарын санауымыз керек.

Аңғал көзқарас - барлық мүмкін жолдарды жасап, содан кейін оларды санау. Бірақ бұл тәсіл көп уақытты қажет етеді. Уақыттың күрделілігін азайту үшін әр түрлі тәсілдерді қарастырған жөн. Біз аңғалдық көзқараста қарастырған әдіс - бұл рекурсивті 0-ші қадамнан бастауға болатын шешім. Содан кейін әрбір рекурсивті қоңырауда i + 1, i + 2 және i + 3 қадамдарына өтіңіз. N-ші қадамға жеткенде есептегішті көбейтіңіз. Осылайша, есептегіш n-ші қадамға жету жолдарының санын сақтайды. Бірақ бұл қадам сол проблемаларды қайта-қайта есептейді. Бұл шешімді оңтайландыру үшін біз қолданамыз Динамикалық бағдарламалау.

Сондай-ақ, қараңыз
Кейінгі өсіп келе жатқан максималды өнім

Динамикалық бағдарламалау шешімінде біз ith қадамында тұрмыз деп есептейміз. І қадамға жету жолдарының саны i-1 қадамнан, i-2 қадамнан немесе i-3 қадамнан тұрады. Сонымен, формальды түрде айтатын болсақ, жолдар [i] = жолдар [i-1] + жолдар [i-2] + жолдар [i-3], осы рекурсивті формуланы қолданады. Біз өз мәселемізді шешеміз.

код  

1-ші, 2-ші немесе 3-ші қадамдар арқылы баспалдаққа жету жолдарын санауға арналған C ++ коды

#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

1-ші, 2-ші немесе 3-ші қадамдар арқылы баспалдаққа жету жолдарын санау үшін Java коды

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

Күрделілікті талдау  

Уақыттың күрделілігі

O (N), өйткені біз циклды n-ші қадамға дейін орындауымыз керек. Демек, бізде динамикалық бағдарламалау тұрғысынан 0-ден n-ге дейінгі жалғыз күй болды, ал ауысу құны O (1) құрайды. Осылайша уақыттың күрделілігі сызықтық болып табылады.

Ғарыштың күрделілігі

O (N), өйткені біз 1-өлшемді DP массивін құруымыз керек. Шешімнің кеңістіктегі күрделілігі сызықтық болып табылады.