قدم 1 ، 2 يا 3 استعمال ڪندي نائين اسٽئر تي پهچڻ جا طريقا ڳڻيو


تڪليف جي سطح آسان
بار بار پڇڻ ۾ Amazon ڪوڊشن اي صحت Microsoft جي مونفيرف ليبز PayPal سليمان وساڻ
گڏجاڻي متحرڪ پروگرامنگ

مسئلو ”قدم 1 ، 2 ، يا 3 استعمال ڪندي نائين سيئر تائين پهچڻ جا طريقا ٻُڌاين ٿا ته توهان زمين تي بيٺا آهيو. هاڻي توهان کي اسٽير جي آخر تائين پهچڻ جي ضرورت آهي. تنهن ڪري آخر تائين پهچي ڪيترا ئي طريقا آهن جيڪڏهن توهان صرف 1 ، 2 ، يا 3 قدم کودائي سگهو ٿا؟

مثال

قدم 1 ، 2 يا 3 استعمال ڪندي نائين اسٽئر تي پهچڻ جا طريقا ڳڻيو

2
2

وضاحت

2 طريقا آهن ڇاڪاڻ ته يا ته سڌو اسان سڌو زمين کان 2 قدم تي پهچي چڪا آهيون يا پهرين اسان پهرين اسٽيئر تي پهچي پوءِ اڳتي وڌون ٿا.

چرچو

مسئلو اسان کي ڪيترين ئي طريقن سان پڇيندي گهرائي جي ڏاڪڻ تائين پهچڻ جي گهر ڪئي آهي جيئن اسين زمين کان شروع ڪريون. تنهن ڪري غور ڪريو ته سيٺ ٻه قدم آهن. ته پوءِ 2 ممڪن طريقا آهن ، يا ته توهان پهرين مرحلي تي پهرين مرحلي تي يا پهرين مرحلي کان پهرين مرحلي تائين ۽ پوءِ 2 کان. ساڳي طرح ، اسان کي 2 ، 1 ، يا 2 جي قدم استعمال ڪندي نائين اسٽئر تي پهچڻ جا طريقا ڳڻپ ڪرڻ گهرجن.

هڪ غيرجانبدار طريقو اهو آهي ته هر ممڪن طريقا پيدا ڪري ۽ پوءِ انهن کي ڳڻپ. پر اهو طريقي سان وقتائتو ٿيندو. ان ڪري وقت جي پيچيدگي گهٽائڻ لاءِ اسان کي ڪجهه مختلف طريقن سان سوچڻ گهرجي. جنهن طريقي سان اسان نون طريقن تي بحث ڪيو آهي اهو آهي ٻيهر حل جتي توهان 0 واري قدم کان شروع ڪري سگهو ٿا. پوء هر recursive ڪال ۾ ، قدم + 1 ، i + 2 ۽ I + 3 ڏانهن وڃو. جڏهن توهان نائين قدم تي پهچي ويا آهيو ته ڪٽر وارا به وڌي وڃو. انهي طريقي سان آخر ۾ ڪائونٽر نون قدم تي پهچڻ لاءِ طريقن جي تعداد کي اسٽور ڪري ٿو. پر اهو قدم ساڳيو مسئلن کي بار بار ٻڌائيندو آهي. تنهنڪري هن حل کي بهتر بڻائڻ لاءِ اسين استعمال ڪندا آهيون متحرڪ پروگرامنگ.

متحرڪ پروگرامنگ حل ۾ ، اسان سمجهون ٿا ته اسان ـ ڏهين قدم تي بيٺا آهيون. پوء ith قدم تائين پھچڻ جا طريقا I-1 قدم ، I-2 قدم يا آئي 3 قدم کان. تنهنڪري رسمي طور ڳالهائڻ ، طريقا [i] = طريقا [i-1] + طريقا [i-2] + طريقا [i-3] ، هن recursive فارمولا کي استعمال ڪندي. اسان پنهنجو مسئلو حل ڪنداسين

ڪوڊ

قدم 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 کان ن تائين ۽ منتقلي جي قيمت او (1) آهي. ان ڪري وقت جي پيچيدگي سڌي آهي.

خلائي پيچيدگي

اي (اين) ، جتان اسان کي 1-D DP ترتيب ڏيڻ جي ضرورت آهي. حل جي خلائي پيچيدگي لڪير آهي.