चरण १, २ वा using प्रयोग गरेर nth सीढीमा पुग्ने तरिकाहरू गणना गर्नुहोस्  


कठिनाई तह सजिलो
बारम्बार सोधिन्छ अमेजन CodeNation जीई हेल्थकेयर माइक्रोसफ्ट मूनफ्रग ल्याबहरू PayPal Uber
संयुक्त डायनामिक प्रोग्रामिंग

समस्या "चरण १, २, वा using प्रयोग गरेर nth सीढी पुग्ने तरिकाहरू गणना गर्नुहोस्" भन्छ कि तपाईं जमीनमा उभिनु भएको छ। अब तपाइँले भर्या .्गको छेउमा पुग्नु पर्छ। त्यसोभए अन्तमा पुग्न कति तरिकाहरू छन् यदि तपाईं मात्र १, २, वा steps चरण उफ्न सक्नुहुन्छ?

उदाहरणका  

चरण १, २ वा using प्रयोग गरेर nth सीढीमा पुग्ने तरिकाहरू गणना गर्नुहोस्पिन

2
2

स्पष्टीकरण

त्यहाँ २ तरिकाहरू छन् किनकि कि हामी सिधा जमीनबाट सीधा दोस्रो चरणमा पुग्छौं वा पहिले हामी पहिलो सीढीमा पुग्छौं र अगाडि बढ्छौं।

दृष्टिकोण  

समस्याले हामीलाई सिँढीको छेउमा पुग्ने पूर्ण भिन्न संख्याहरू सोध्छ जुन हामी भूमिबाट शुरू गर्छौं। त्यसोभए सीढीहरूमा विचार गर्नुहोस् २ चरणहरू छन्। त्यसोभए त्यहाँ २ सम्भावित तरिकाहरू छन्, कि त तपाईं सीधा दोस्रो चरणमा कदम चाल्नुहोस् वा पहिलो चरण पहिलो चरणमा र त्यसपछि दोस्रोमा। त्यस्तै, हामीले चरणहरू १, २, वा using प्रयोग गरेर nth सीढी पुग्ने तरिकाहरू गणना गर्न आवश्यक छ।

एक भोली दृष्टिकोण सबै सम्भावित तरिकाहरू उत्पन्न गर्न र त्यसपछि ती गणना गर्नुहोस्। तर यो दृष्टिकोण समय खपत हुने छ। यस प्रकार समय जटिलता कम गर्न हामीले केहि बिभिन्न तरिकाहरूका बारे विचार गर्नुपर्छ। हामीले भोली दृष्टिकोणमा छलफल गरेको विधि एक हो रिकर्सिव समाधान जहाँ तपाईं ० औं चरणबाट सुरू गर्न सक्नुहुन्छ। त्यसो भए प्रत्येक रिकर्सिभ कलमा, i + १, i + २, र i + step मा जानुहोस्। जब तपाईं nth चरण वृद्धि काउन्टर पुग्नुहुन्छ। यस तरीकामा अन्तमा काउन्टरले nth चरणमा पुग्न धेरै तरिकाहरू तरीका भण्डारण गर्दछ। तर यो कदम फेरि र फेरि उही समस्याहरू recomputes। त्यसोभए यो समाधानलाई अनुकूलन गर्न हामी प्रयोग गर्दछौं डायनामिक प्रोग्रामिंग.

पनि हेर्नुहोस्
एक बढ्दो अनुगामीको अधिकतम उत्पादन

डायनामिक प्रोग्रामिंग समाधानमा हामी विचार गर्छौं कि हामी ith चरणमा उभिरहेका छौं। त्यसो भए ith चरणमा पुग्न मार्गहरूको संख्या आई -१ चरण, i-२ चरण, वा i-1 चरणबाट हो। औपचारिक रूपमा बोल्दै, तरिका [i] = तरीके [i-2] + तरिका [i-3] + तरिका [i-1], यो रिकर्सिभ सूत्र प्रयोग गरेर। हामी हाम्रो समस्या समाधान गर्नेछौं।

कोड  

C ++ कोड गणना गर्न उपायहरू १, २ वा n प्रयोग गरेर नवौं सीढीमा पुग्न

#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

जाभा कोड चरणहरू १, २ वा using प्रयोग गरेर नौौं सीढीमा पुग्न उपायहरू गणना गर्न

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), किनकि हामीले nth चरण सम्म एक लूप चल्नु पर्छ। त्यसैले डायनामिक प्रोग्रामिंगको हिसाबले, हामीसँग एकल राज्य ० देखि n सम्म रहेको र संक्रमण लागत O (१) हो। यस प्रकार समय जटिलता रैखिक छ।

ठाउँ जटिलता

O (N), किनकि हामीले 1-D DP एर्रे सिर्जना गर्न आवश्यक पर्दछ। समाधानको स्थान जटिलता रैखिक छ।