ڊيگهه ، وڌ ۾ وڌ وڌ ۾ وڌ ڀا aي اي ، ب ۽ سي


تڪليف جي سطح وچولو
بار بار پڇڻ ۾ Amazon ڪاروڪ ByteDance Citrix گوگل ٽراداتا سليمان وساڻ
متحرڪ پروگرامنگ

مسئلو ”لمبائي جي وڌ کان وڌ ڀا aي a ، b ۽ c“ ٻڌائي ٿي ته توهان کي مثبت عدد اين. ڏنو وڃي ٿو ، ۽ توهان کي لمبائي جي وڌ کان وڌ عدد اي ، ب ، ۽ سي ڳولڻ جي ضرورت آهي جيڪي اين.

مثال

ڊيگهه ، وڌ ۾ وڌ وڌ ۾ وڌ ڀا aي اي ، ب ۽ سي

N = 7
a = 5, b = 2, c = 3
3

وضاحت

هتي جيڪڏهن اسين لالچي طريقي سان وڃون ، نن smallestن حصن سان نن theن حصن کي ڪٽڻ جي ڪوشش ڪري رهيا آهيون (= 2). اسان ماپ جو آخري حصو نه ٺاهي سگهنداسين. اهڙي طرح اسان ڊيگهه 1 کي ٻن 4 لمبن ڀا andن ۽ هڪ 2 جي ڊيگهه حصي سان ورهايو.

چرچو

مسئلو اسان کي مهيا ڪندو آهي مثبت اڪثريت ن ، ۽ ڪجهه ٻين انٽيگرنز اي ، بي ، سي. هتي اسان عدد کي لمبائي ۾ تقسیم ڪرڻ چاهيون ٿا a ، b ، ۽ c. اسان کي اين کي ورهائڻ جي ضرورت آهي ته ڀا ofن جو تعداد وڌ کان وڌ آهي. تنهنڪري مسئلو حل ڪرڻ لاءِ ، اچو ته پهرين لالچي طريقي سان ڪوشش ڪريون. مسئلو کي حل ڪرڻ لاءِ لالچي طريقي سان نن aن ، اي ، ۽ ج جي چونڊ ٿيندي آهي. هاڻي اسان ن کي حصن ۾ گھٽ ۾ گھٽ ڊيگهه سان ورهايو آهي. پر انهي جي پڪڙ آهي ، ڇا جيڪڏهن نن theڙو ڀا Nو اين کي ورهائيندو نه آهي؟ پوءِ اسان کي ڇڏيو ويندو باقي حصي سان جنهن کي بڻائڻ ممڪن نه آهي. تنهن ڪري ، انهي مان تصديق ٿئي ٿي ته اسان ڪجهه ڪيسن ۾ لالچي انداز سان استعمال ڪندي جواب ڳولي نه سگهنداسين.

تنهن ڪري ، هن بدران حرص واري طريقي سان استعمال ڪندي. اسان استعمال ڪندي مسئلو حل ڪيو مفاهمت. اسان هڪ فنڪشن ٺاهيون ٿا جيڪو اسان کي اين لاءِ جواب ڏئي ٿو ، پوءِ اهو فنڪشن قدر ، ن ، ۽ اين سي سان پاڻ کي سڏائي ٿو. اهڙيءَ طرح اصل مسئلو نن smallerن ضمني مسئلن ۾ ورهائجي ويو آهي. اسان استعمال ڪندي هن recursive فنڪشن جي توسيعاتي وقت جي پيچيدگي کي گهٽائي سگھون ٿا متحرڪ پروگرامنگ. ڊي پي سان پروگرام لڪيڪ وقت ۾ هلندو. ڇو ته اسان ڊي پي جي ترتيب ٺاهي سگهنداسين جيڪا نن subن ذيلي مسئلن جو جواب ذخيرو ڪري ڇڏيندي. ۽ جڏهن به انهن جو نتيجو گهربل هوندو آهي ته اسين ٻيهر ڳڻپ ڪرڻ بدران انهن کي استعمال ڪندا آهيون جئين اسان تراشي واري حل ۾.

ڪوڊ

سي ++ ڪوڊ لمبائي جي وڌ کان وڌ حصن کي ڳولڻ لاءِ اي ، ب ۽ سي

#include <bits/stdc++.h>
using namespace std;

int main()
{
  int n = 7, a = 5, b = 2, c = 3;
  int dp[n + 1];
  memset(dp, -1, sizeof(dp));
  // base case
  dp[0] = 0;
  for (int i = 0; i < n; i++)
  {
    if (dp[i] != -1) {
            if(i + a <= n )dp[i + a] = max(dp[i] + 1, dp[i + a]);
            if(i + b <= n )dp[i + b] = max(dp[i] + 1, dp[i + b]);
            if(i + c <= n )dp[i + c] = max(dp[i] + 1, dp[i + c]);
    }
  }
    cout<<dp[n];
}
3

جاوا ڪوڊ لمبائي جي وڌ کان وڌ حصن کي ڳولڻ لاءِ ، a ۽ b

import java.util.*;
class Main{
  public static void main(String[] args)
  {
    int n = 7, a = 5, b = 2, c = 3;
    int dp[] = new int[n+1];
    for(int i=0;i<=n;i++)dp[i] = -1;
    // base case
    dp[0] = 0;
    for (int i = 0; i < n; i++)
    {
      if (dp[i] != -1) {
              if(i + a <= n )dp[i + a] = Math.max(dp[i] + 1, dp[i + a]);
              if(i + b <= n )dp[i + b] = Math.max(dp[i] + 1, dp[i + b]);
              if(i + c <= n )dp[i + c] = Math.max(dp[i] + 1, dp[i + c]);
      }
    }
    System.out.println(dp[n]);
  }
}
3

پيچيدگي تجزيي

وقت جي پيچيدگي

اي (اين) ، ڇاڪاڻ ته اسان مڪمل طور تي ڏنل اڪثريت تائين هڪ لوپ هليا. ان ڪري وقت جي پيچيدگي سڌي آهي.

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

اي (اين) ، ڇاڪاڻ ته وقتي نتيجن کي محفوظ ڪرڻ لاءِ اسان کي ٻيهر ڳڻپيوڪر کان بچاءُ لاءِ 1D DP ترتيب ڏيڻي پئي. اھڙيءَ طرح خلائي پيچيدگيءَ پڻ لڪير آھي.