પગલું 1, 2 અથવા 3 નો ઉપયોગ કરીને નવમી સીડી સુધી પહોંચવાની રીતોની ગણતરી કરો


મુશ્કેલી સ્તર સરળ
વારંવાર પૂછવામાં આવે છે એમેઝોન કોડનેશન જીઇ હેલ્થકેર માઈક્રોસોફ્ટ મૂનફ્રોગ લેબ્સ પેપાલ ઉબેર
સંયુક્ત ડાયનેમિક પ્રોગ્રામિંગ

સમસ્યા "પગલું 1, 2, અથવા 3 નો ઉપયોગ કરીને નવમી સીડી સુધી પહોંચવાની રીતોની ગણતરી કરો" કહે છે કે તમે જમીન પર .ભા છો. હવે તમારે સીડીના અંત સુધી પહોંચવાની જરૂર છે. તેથી જો તમે ફક્ત 1, 2 અથવા 3 પગથિયાં જ કૂદી શકો તો અંત સુધી પહોંચવાની કેટલી બધી રીતો છે?

ઉદાહરણ

પગલું 1, 2 અથવા 3 નો ઉપયોગ કરીને નવમી સીડી સુધી પહોંચવાની રીતોની ગણતરી કરો

2
2

સમજૂતી

ત્યાં 2 રસ્તાઓ છે કારણ કે કાં તો આપણે સીધા જ જમીન પરથી સીધા જ બીજા પગલા પર પહોંચીએ છીએ અથવા પહેલા આપણે પહેલી સીડી પર પહોંચ્યા પછી આગળ વધીએ.

અભિગમ

સમસ્યા અમને સીડીના અંત સુધી પહોંચવાની કુલ વિવિધ સંખ્યાઓ પૂછે છે જેમ કે આપણે જમીનથી શરૂ કરીએ છીએ. તેથી ધ્યાનમાં સીડી 2 પગલાંઓ છે. પછી ત્યાં 2 સંભવિત રીતો, કાં તો તમે સીધા જ બીજા પગલા પર જાઓ અથવા પહેલું પગલું 2 લી પગલું અને પછી 1 જી. એ જ રીતે, આપણે પગલાં 2, 1, અથવા 2 નો ઉપયોગ કરીને નવમી સીડી સુધી પહોંચવાની રીતોને ગણવાની જરૂર છે.

એક નિષ્કપટ અભિગમ એ બધી સંભવિત રીત બનાવવી અને પછી તેને ગણતરી કરવી. પરંતુ આ અભિગમ સમય માંગી લેશે. આમ સમયની જટિલતાને ઘટાડવા માટે આપણે કેટલીક જુદી જુદી રીતો વિશે વિચારવું જોઇએ. નિષ્કપટ અભિગમમાં આપણે જે પદ્ધતિની ચર્ચા કરી છે તે છે પુનરાવર્તિત સોલ્યુશન જ્યાં તમે 0 થી પગલાથી પ્રારંભ કરી શકો છો. પછી દરેક પુનરાવર્તિત ક callલમાં, i + 1, i + 2 અને i + 3 પર જાઓ. જ્યારે તમે નવમા પગલામાં વધારો કરો ત્યારે કાઉન્ટર વધો. આ રીતે અંતે કાઉન્ટર નવમા પગલા સુધી પહોંચવાની સંખ્યાની સંખ્યા સંગ્રહિત કરે છે. પરંતુ આ પગલું એ જ સમસ્યાઓ ફરીથી અને ફરીથી સુધારે છે. તેથી અમે આ સોલ્યુશનને optimપ્ટિમાઇઝ કરવા માટે ડાયનેમિક પ્રોગ્રામિંગ.

ડાયનેમિક પ્રોગ્રામિંગ સોલ્યુશનમાં, અમે ધ્યાનમાં લઈએ છીએ કે અમે ith સ્ટેપ પર standingભા છીએ. પછી આઈથ સ્ટેપ સુધી પહોંચવાની રીતોની સંખ્યા, આઈ -1 પગલું, આઇ -2 પગલું અથવા આઇ -3 પગલું છે. Recપચારિક રીતે કહીએ તો, આ રીકર્સિવ ફોર્મ્યુલાનો ઉપયોગ કરીને, [i] = માર્ગો [i-1] + માર્ગો [i-2] + માર્ગો [i-3]. અમે અમારી સમસ્યા હલ કરીશું.

કોડ

પગલું 1, 2 અથવા 3 નો ઉપયોગ કરીને નવમી સીડી સુધી પહોંચવાની રીતો ગણતરી માટે સી ++ કોડ

#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 સુધીની એક જ રાજ્ય હતી અને સંક્રમણ ખર્ચ O (1) છે. આમ સમય જટિલતા રેખીય છે.

અવકાશ જટિલતા

ઓ (એન), કારણ કે આપણે 1-D DP એરે બનાવવાની જરૂર છે. સોલ્યુશનની જગ્યાની જટિલતા રેખીય છે.