படி 1, 2 அல்லது 3 ஐப் பயன்படுத்தி n வது படிக்கட்டுக்குச் செல்வதற்கான வழிகளைக் கணக்கிடுங்கள்


சிரமம் நிலை எளிதாக
அடிக்கடி கேட்கப்படுகிறது அமேசான் கோட்நேஷன் GE ஹெல்த்கேர் மைக்ரோசாப்ட் மூன்ஃப்ராக் ஆய்வகங்கள் பேபால் கிழித்து
கூட்டு டைனமிக் புரோகிராமிங்

“படி 1, 2, அல்லது 3 ஐப் பயன்படுத்தி n வது படிக்கட்டுக்குச் செல்வதற்கான வழிகளைக் கணக்கிடுங்கள்” என்ற சிக்கல் நீங்கள் தரையில் நிற்கிறீர்கள் என்று கூறுகிறது. இப்போது நீங்கள் படிக்கட்டின் முடிவை அடைய வேண்டும். நீங்கள் 1, 2, அல்லது 3 படிகள் மட்டுமே செல்ல முடிந்தால் முடிவை அடைய எத்தனை வழிகள் உள்ளன?

உதாரணமாக

படி 1, 2 அல்லது 3 ஐப் பயன்படுத்தி n வது படிக்கட்டுக்குச் செல்வதற்கான வழிகளைக் கணக்கிடுங்கள்

2
2

விளக்கம்

2 வழிகள் உள்ளன, ஏனென்றால் நாம் தரையில் இருந்து நேரடியாக 2 வது படியை நேரடியாக அடைகிறோம் அல்லது முதலில் 1 வது படிக்கட்டுக்கு வந்து பின்னர் முன்னேறுவோம்.

அணுகுமுறை

நாங்கள் தரையில் இருந்து தொடங்கும் படிக்கட்டின் முடிவை அடைய மொத்த வேறுபட்ட வழிகளை சிக்கல் கேட்கிறது. எனவே படிக்கட்டுகளில் 2 படிகள் உள்ளன. பின்னர் 2 சாத்தியமான வழிகள் உள்ளன, நீங்கள் நேரடியாக 2 வது படிக்கு அல்லது முதல் படிக்கு 1 வது படிக்கு, பின்னர் 2 வது படிக்கு செல்லுங்கள். இதேபோல், 1, 2, அல்லது 3 படிகளைப் பயன்படுத்தி n வது படிக்கட்டுக்குச் செல்வதற்கான வழிகளை நாம் எண்ண வேண்டும்.

ஒரு அப்பாவி அணுகுமுறை என்பது சாத்தியமான எல்லா வழிகளையும் உருவாக்கி அவற்றை எண்ணுவதாகும். ஆனால் இந்த அணுகுமுறை நேரத்தை எடுத்துக்கொள்ளும். இதனால் நேர சிக்கலைக் குறைக்க நாம் வேறு சில வழிகளைப் பற்றி சிந்திக்க வேண்டும். அப்பாவியாக அணுகுமுறையில் நாம் விவாதித்த முறை a சூத்திர 0 வது படியிலிருந்து நீங்கள் தொடங்கக்கூடிய தீர்வு. ஒவ்வொரு சுழல்நிலை அழைப்பிலும், i + 1, i + 2 மற்றும் i + 3 படிகளுக்குச் செல்லவும். நீங்கள் n வது படி அடையும் போது கவுண்டரை அதிகரிக்கும். இந்த வழியில் இறுதியில் கவுண்டர் n வது படி அடைய பல வழிகளை சேமிக்கிறது. ஆனால் இந்த படி அதே பிரச்சினைகளை மீண்டும் மீண்டும் மீண்டும் செய்கிறது. எனவே இந்த தீர்வை மேம்படுத்த நாம் பயன்படுத்துகிறோம் டைனமிக் புரோகிராமிங்.

டைனமிக் புரோகிராமிங் தீர்வில், நாங்கள் ஐடி படியில் நிற்கிறோம் என்று கருதுகிறோம். Ith 1 படி, i-2 படி, அல்லது i-3 படி ஆகியவற்றிலிருந்து ith படிநிலையை அடைவதற்கான வழிகளின் எண்ணிக்கை. எனவே முறையாகப் பேசினால், வழிகள் [i] = வழிகள் [i-1] + வழிகள் [i-2] + வழிகள் [i-3], இந்த சுழல்நிலை சூத்திரத்தைப் பயன்படுத்தி. நாங்கள் எங்கள் பிரச்சினையை தீர்ப்போம்.

குறியீடு

படி ++, படி 1, 2 அல்லது 3 ஐப் பயன்படுத்தி 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

படி 1, 2 அல்லது 3 ஐப் பயன்படுத்தி n வது படிக்கட்டுக்குச் செல்வதற்கான வழிகளை எண்ணுவதற்கான ஜாவா குறியீடு

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

சிக்கலான பகுப்பாய்வு

நேர சிக்கலானது

ஓ (என்), ஏனென்றால் நாம் n வது படி வரை ஒரு சுழற்சியை இயக்க வேண்டும். எனவே டைனமிக் புரோகிராமிங்கைப் பொறுத்தவரை, எங்களிடம் 0 முதல் n வரையிலான ஒற்றை நிலை இருந்தது மற்றும் மாற்றம் செலவு O (1) ஆகும். இதனால் நேர சிக்கலானது நேரியல்.

விண்வெளி சிக்கலானது

ஓ (என்), நாம் 1-D டிபி வரிசையை உருவாக்க வேண்டும் என்பதால். தீர்வின் இட சிக்கலானது நேரியல் ஆகும்.