ደረጃ 1 ፣ 2 ወይም 3 ን በመጠቀም ወደ ኛ ደረጃ ለመድረስ መንገዶችን ይቆጥሩ  


የችግር ደረጃ ቀላል
ውስጥ በተደጋጋሚ ተጠየቀ አማዞን የኮድ ቁጥር GE የጤና የ Microsoft የሞንፎርግ ቤተ ሙከራዎች የ 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 ይሂዱ ፡፡ ወደ ዘጠኝ ኛ ደረጃ ሲጨምሩ ቆጣሪውን ይጨምሩ ፡፡ በዚህ መንገድ በመጨረሻ ቆጣሪው ወደ ዘጠነኛው ደረጃ ለመድረስ ብዙ መንገዶችን ያከማቻል ፡፡ ግን ይህ እርምጃ ተመሳሳይ ችግሮችን እንደገና ይደግማል ፡፡ ስለዚህ እኛ የምንጠቀምበትን ይህንን መፍትሄ ለማመቻቸት ተለዋዋጭ ፕሮግራም.

ተመልከት
እየጨመረ የመጣው ከፍተኛ ምርት

በተለዋጭ የፕሮግራም አወጣጥ መፍትሄ ፣ እኛ በእሾህ ደረጃ እንደቆምን እንመለከታለን ፡፡ ከዚያ ወደ ith ደረጃ ለመድረስ መንገዶች ብዛት ከ i-1 ደረጃ ፣ i-2 ደረጃ ወይም ከ i-3 ደረጃ ነው። ስለዚህ በመደበኛነት መናገር ፣ መንገዶች [i] = ways [i-1] + ways [i-2] + ways [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 ን በመጠቀም ወደ ነት ደረጃ ለመድረስ መንገዶችን ለመቁጠር የጃቫ ኮድ

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 የሚደርስ አንድ ነጠላ ግዛት ነበረን እና የሽግግሩ ዋጋ ኦ (1) ነው ፡፡ ስለዚህ የጊዜ ውስብስብነት መስመራዊ ነው።

የቦታ ውስብስብነት

ኦ (ኤን) ፣ ባለ 1-ዲ ዲፒ ድርድር መፍጠር ስላለብን ፡፡ የመፍትሔው የቦታ ውስብስብነት መስመራዊ ነው።