صحيح نمبر مثلث ۾ رستي جي وڌ کان وڌ رقم


تڪليف جي سطح وچولو
بار بار پڇڻ ۾ Citrix ڊي شاه سڌو Expedia
متحرڪ پروگرامنگ Math

مسئلو ”صحيح نمبر واري مثلث ۾ رستي جي وڌ کان وڌ رقم“ بيان ڪري ٿي ته توهان کي ڪجهه ڏنو ويو آهي جيتريون صحيح عدد مثلث جي شڪل ۾. وڌ کان وڌ رقم ڳوليو جيڪڏهن توهان مٿي کان شروع ڪيو ۽ بي بنياد طرف وڌو ته اهڙي طرح توهان هن جي اندر يا هن جي سا toي طرف هڪ جاءِ تي صرف سيل کي منتقل ڪيو.

مثال

صحيح نمبر مثلث ۾ رستي جي وڌ کان وڌ رقم

3 // Number of rows in the right number triangle
1
3 2
4 10 12
15

وضاحت

وڌ کان وڌ رقم جيڪا مٿي کان مٿي تائين وڃي وڃڻ سان حاصل ڪري سگهجي ٿي 15. اها هيٺين مرحلن مان حاصل ڪري سگهجي ٿي: 1 -> 2 -> 12. اهو بهتر سمجهي سگهجي ٿو مٿي واري تصوير مان.

چرچو

اسان وٽ اڳ ئي ڪجھ ٻيا مسئلا آھن جيڪي ھن مسئلي سان گڏ آھن. اسان کي ڳولڻ لاءِ مسئلا حل ڪيا هئا وڌ ۾ وڌ, گھٽ ۾ گھٽ هڪ مثلث ۾ جيتري رستو. اهو مسئلو انهن مسئلن جو ٿورڙو تڪرار آهي. تنهن ڪري شرط جيڪا حرڪت تي لاڳو ٿئي ٿي اها آهي ته توهان موجوده سيل کان بلڪل هيٺ يا صرف هيٺ وڃي سگهو ٿا. ۽ توهان مٿين کان شروع ڪريو ٿا ته مٿئين مٿي کان آهي. پوءِ تري ۾ پھچ.

هڪ طريقو استعمال ڪرڻ آهي مفاهمت. اسان هڪ فنڪشن ٺاهي سگهنداسين جيڪي دلائل طور اشارن کي وٺندا ۽ وڌ کان وڌ ڳولي سگهندا جيڪي انهي سيل مان حاصل ڪيا ويندا. ان طريقي سان اسان جواب ٻيهر ڳوليندا آهيون. پر اهو مسئلو وقت کي نقصان پهچائيندو آهي ۽ وقت کي يقيني طور تي ختم ڪري سگهندو. اهڙيءَ طرح مسئلي کي موثر طريقي سان حل ڪرڻ. اسان يا ته انهن يادگارن ڪالن جو نتيجو ياد رکون ٿا. يا استعمال ڪريو متحرڪ پروگرامنگ انهي کي حل ڪرڻ اسان هيٺيان طريقي سان بحث ڪنداسين ، جيڪو پهرين نن smallerن نن problemsن مسئلن جو نتيجو طئي ڪندو ۽ پوءِ انهن نتيجن کي ملائڻ اصل مسئلي جو جواب ڳوليندو.

اسان بنيادي ڪيس جي وضاحت ڪيون ٿا ، ڊي پي [0] [0] کي ڀرڻ سان ، ابتدائي انپٽ صف جي سيل سان. ڇاڪاڻ ته اسان انهي سيل کان ڪنهن ٻئي خاني تائين پهچي نٿا سگهون ۽ اها شروعات آهي. انهي کان پوءِ ، اسان ٻئي قطار ڏانهن وڃون ٿا. هتي اسان وٽ هڪ ٻئي جو خانداني طريقو آهي. ۽ اختيار آهي مٿين چوٽيس خاني کي چونڊڻ. پوءِ هن قطار کان پوءِ ، سڀني خاني جي لاءِ اسان کي اهو فيصلو ڪرڻو پوندو ته ڪهڙي خاني کي چونڊيو وڃي ته يا ته صرف سيل تي يا جيڪي صرف موجوده خاني جي کاٻي پاسي آهن. هي سڀ ٿيڻ بعد ، اسان ڊي پي ٽيبل جي آخري قطار تي وڌ کان وڌ ذخيرو ڪري وٺون ٿا.

ڪوڊ

سي نمبر+ ھڪڙي رستي واري وڌ کان وڌ رقم ڳولڻ لاءِ سي نمبر نمبر ٽانٽل ۾

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

int main(){
    int n;cin>>n;
    int input[n][n];
    for(int i=0;i<n;i++)
        for(int j=0;j<=i;j++)
            cin>>input[i][j];
  if (n > 1)
    input[1][1] = input[1][1] + input[0][0];
    input[1][0] = input[1][0] + input[0][0];
  for(int i = 2; i < n; i++){
        // because the boundary cells have only a single option
    input[i][0] = input[i][0] + input[i-1][0];
    input[i][i] = input[i][i] + input[i-1][i-1];
    for (int j = 1; j < i; j++)
            input[i][j] = input[i][j] + max(input[i-1][j-1], input[i-1][j]);
  }

  int ans = INT_MIN;
  for(int i=0;i<n;i++)
        ans = max(ans, input[n-1][i]);
  cout<<ans;
}
3
1
3 2
4 10 12
15

جاوا ڪوڊ هڪ رستي جي وڌ کان وڌ رقم ڳولڻ لاءِ صحيح تعداد واري مثلث ۾

import java.util.*;
class Main{
  public static void main(String[] args)
  {
    Scanner sc = new Scanner(System.in);
      int n = sc.nextInt();
      int input[][] = new int[n][n];
      for(int i=0;i<n;i++)
          for(int j=0;j<=i;j++)
              input[i][j] = sc.nextInt();;
    if (n > 1)
      input[1][1] = input[1][1] + input[0][0];
      input[1][0] = input[1][0] + input[0][0];
    for(int i = 2; i < n; i++){
          // because the boundary cells have only a single option
      input[i][0] = input[i][0] + input[i-1][0];
      input[i][i] = input[i][i] + input[i-1][i-1];
      for (int j = 1; j < i; j++)
              input[i][j] = input[i][j] + Math.max(input[i-1][j-1], input[i-1][j]);
    }

    int ans = Integer.MIN_VALUE;
    for(int i=0;i<n;i++)
          ans = Math.max(ans, input[n-1][i]);
    System.out.println(ans);
  }
}
3
1
3 2
4 10 12
15

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

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

اي (اين ^ 2) ، جتي N ٽڪنڊي ۾ قطار جو تعداد ٻڌائيندو آهي. ڇاڪاڻ ته اھو عنصرن جو تعداد آھي جيڪي آخري قطار ۾ آھن.

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

اي (1) ، ڇاڪاڻ ته اسان ڊي پي ميز لاءِ ساڳئي انٽري صف استعمال ڪئي آهي. اهڙيءَ طرح خلائي پيچيدگي مستقل آهي ڇو ته اسان کي نئين ڊي پي صف ٺاهڻ لاءِ جڳهه ڪونه ورتي وئي.