Հաշվեք 1-րդ աստիճանին հասնելու ուղիները ՝ օգտագործելով 2, 3 կամ XNUMX քայլերը


Դժվարության մակարդակ Հեշտ
Հաճախակի հարցնում են Amazon CodeNation GE Healthcare Microsoft Moonfrog լաբորատորիաներ PayPal Uber
Կոմբինատորական Դինամիկ ծրագրավորում

«Հաշվեք ուղիները, որպեսզի հասնեք 1-րդ աստիճանին` օգտագործելով 2, 3 կամ 1 քայլերը », ասում է, որ դուք կանգնած եք գետնին: Այժմ դուք պետք է հասնեք սանդուղքի ավարտին: Այսպիսով, քանի՞ ուղիներ կան ավարտին հասնելու համար, եթե կարողանաք ցատկել ընդամենը 2, 3 կամ XNUMX քայլ:

Օրինակ

Հաշվեք 1-րդ աստիճանին հասնելու ուղիները ՝ օգտագործելով 2, 3 կամ XNUMX քայլերը

2
2

բացատրություն

Կա 2 ճանապարհ, որովհետև կա՛մ մենք անմիջապես գետնից հասնում ենք 2-րդ աստիճանին, կա՛մ նախ հասնում ենք 1-ին աստիճանին, ապա շարժվում առաջ:

Մոտեցում

Խնդիրը մեզ հարցնում է սանդուղքի ավարտին հասնելու ուղիների ընդհանուր տարբեր քանակով, որպեսզի մենք սկսենք գետնից: Այսպիսով, հաշվի առեք, որ աստիճաններն ունեն 2 աստիճան: Դրանից հետո կա 2 հնարավոր ճանապարհ, կամ դու ուղղակիորեն քայլում ես դեպի 2-րդ աստիճան, կամ առաջին քայլը դեպի 1-ին աստիճան, և այնուհետև 2-րդ: Նմանապես, մենք պետք է հաշվենք 1-րդ աստիճանին հասնելու ուղիները ՝ օգտագործելով 2, 3 կամ XNUMX քայլերը:

Միամիտ մոտեցում է ստեղծել բոլոր հնարավոր ուղիները և ապա հաշվել դրանք: Բայց այս մոտեցումը ժամանակատար կլինի: Այսպիսով, ժամանակի բարդությունը նվազեցնելու համար մենք պետք է մտածենք տարբեր ձևերի մասին: Միամիտ մոտեցման մեջ քննարկված մեթոդը ա ռեկուրսիվ լուծում, որտեղ կարող եք սկսել 0-րդ քայլից: Դրանից հետո յուրաքանչյուր ռեկուրսիվ զանգի դեպքում անցեք i + 1, i + 2 և i + 3 քայլերին: Երբ հասնում եք XNUMX-րդ աստիճանը, ավելացրեք հաշվիչը: Այս եղանակով վերջում վաճառասեղանը պահում է XNUMX-րդ աստիճանին հասնելու ձևերի քանակը: Բայց այս քայլը կրկին ու կրկին փոխհատուցում է նույն խնդիրները: Այսպիսով, այս լուծումը օպտիմալացնելու համար մենք օգտագործում ենք Դինամիկ ծրագրավորում.

Դինամիկ ծրագրավորման լուծման մեջ մենք համարում ենք, որ կանգնած ենք երկրորդ քայլին: Այնուհետև երկրորդ աստիճանին հասնելու ուղիների քանակը i-1 քայլից է, i-2 քայլից կամ i-3 քայլից: Այսպիսով, պաշտոնապես ասած, եղանակներ [i] = ուղիներ [i-1] + եղանակներ [i-2] + ուղիներ [i-3] ՝ օգտագործելով այս ռեկուրսիվ բանաձևը: Մենք մեր խնդիրը կլուծենք:

Կոդ

C ++ կոդ ՝ հաշվելու համար 1-րդ աստիճանին հասնելու ուղիները ՝ օգտագործելով 2, 3 կամ XNUMX քայլերը

#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 կամ XNUMX քայլերը

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

Բարդության վերլուծություն

Timeամանակի բարդություն

ՎՐԱ), քանի որ մենք պետք է օղակ աշխատենք մինչև n- րդ քայլը: Այսպիսով, դինամիկ ծրագրավորման առումով մենք ունեինք մեկ պետություն ՝ սկսած 0-ից n, և անցման արժեքը O է (1): Այսպիսով, ժամանակի բարդությունը գծային է:

Տիեզերական բարդություն

ՎՐԱ), քանի որ մենք պետք է ստեղծենք 1-D DP զանգված: Լուծույթի տիեզերական բարդությունը գծային է: