ত্রিভুজটিতে সর্বাধিক পথের যোগফল


কাঠিন্য মাত্রা মধ্যম
প্রায়শই জিজ্ঞাসা করা হয় আরেসিয়াম কোডনেশন জিই হেলথকেয়ার Payu উবার Zoho
ডায়নামিক প্রোগ্রামিং

সমস্যা বিবৃতি

"ত্রিভুজটিতে সর্বাধিক পথের যোগফল" সমস্যাটি আপনাকে উল্লেখ করে যে আপনাকে কিছু পূর্ণসংখ্যা দেওয়া হয়েছে। এই পূর্ণসংখ্যাগুলি একটি ত্রিভুজ আকারে সাজানো হয়। আপনি ত্রিভুজটির শীর্ষ থেকে শুরু করছেন এবং নীচের সারিতে পৌঁছানোর প্রয়োজন। এটি করার জন্য, আপনি পরবর্তী সারিতে সংলগ্ন কক্ষে চলে যান move সুতরাং আপনি যখন নির্ধারিত উপায়ে ত্রিভুজটি নিচে চলে যাচ্ছেন, আপনি সর্বোচ্চ পরিমাণটি কী অর্জন করতে পারবেন?

উদাহরণ

ত্রিভুজটিতে সর্বাধিক পথের যোগফল

  1
 2 3
5 8 1
12

ব্যাখ্যা
আপনি কেবল নিম্নলিখিত পদ্ধতিতে পথটি সরিয়ে নিতে পারেন। 1-> 3-> 8, এই পথটি আপনাকে 12 এর সর্বোচ্চ সীমা অর্জন করবে।

অভিগমন

সুতরাং আমরা কীভাবে ত্রিভুজটিতে সর্বাধিক পাথের যোগফলটি সমাধান করব? এখন অবধি, আমরা এই ধরণের সমস্যার সাথে বেশ পরিচিত familiar যখনই আমাদের এই ধরণের সমস্যা সরবরাহ করা হয়। সর্বদা নিষ্ঠুর বলের পন্থা হ'ল প্রথমে আপনার গন্তব্যে পৌঁছানোর সম্ভাব্য সমস্ত উপায় তৈরি করা। এবং তারপরে প্রতিটি পাথের জন্য যোগফল গণনা করে অনুকূল ফলাফলের জন্য উত্তরটি আপডেট করতে থাকুন। তবে এই পদ্ধতির পক্ষে অত্যন্ত অকার্যকর কারণ এই পদ্ধতির জন্য আমাদের পথগুলি তৈরি করা প্রয়োজন। এবং আমরা জানি যে পাথ জেনারেশন এমন একটি কাজ যা ক্ষতিকারক সময় জটিলতা রয়েছে যা ভাল নয়।

সুতরাং, এটিকে সমাধান করার জন্য আমাদের আরও একটি পদ্ধতির কথা ভাবতে হবে। তারপরে গতিশীল প্রোগ্রামিং আমাদের উদ্ধার আসে। কারণ পথগুলি উত্পন্ন করার পরিবর্তে, যদি আমরা কোনওভাবে জানতে পারি যে কোষ থেকে নীচের সারিতে পৌঁছানোর জন্য সর্বোচ্চটি কী হতে পারে। এই উপায়ে আমরা এটির পাশের কক্ষের জন্য ফলাফলটি পেতে পারি তবে এটির উপরের সারিতে। সুতরাং, আমরা ছোট সাব-প্রবলেমগুলি সমাধান করার জন্য ডিপি ব্যবহার করি। তারপরে সেই সাব-সমস্যার জন্য ফলাফলগুলি সংযুক্ত করে আমরা মূল সমস্যার উত্তর খুঁজে পাই।

প্রথমত, আমরা শেষ সারিতে থাকা ঘরগুলির জন্য উত্তরটি পূরণ করি। আমরা জানি যে আমরা নীচের সারিতে কোষ থেকে শুরু করলে সর্বাধিক যোগফলটি হ'ল এটির সংখ্যা। এর পরে, আমরা নীচের সারির উপরের সারিতে চলে যাই। বর্তমান সারির প্রতিটি কক্ষের জন্য, আমরা নীচের সারিতে এটির সংলগ্ন কক্ষগুলির ডিপি মানগুলি চয়ন করতে পারি। এইভাবে আমরা upর্ধ্বমুখী দিকে এগিয়ে চলি। উপরের সারিতে পৌঁছে আমরা সমস্যাটি শেষ করেছি।

ত্রিভুজটিতে সর্বাধিক পাথের যোগফল খুঁজতে সি ++ কোড

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

int maximumPathSumInTriangle(vector<vector<int>> &input)
{
    int n = input.size();
    // start from row above bottom row
    // since the bottom row cells are the answers themselves
  for(int i=n-2;i>=0;i--)
  {
      // start from left to right in column
    for(int j=0;j<=i;j++)
    {
      if(input[i+1][j] > input[i+1][j+1])
        input[i][j] += input[i+1][j];
      else
        input[i][j] += input[i+1][j+1];
    }
  }
  return input[0][0];
}

int main()
{
    int n;cin>>n; // number of rows
    vector<vector<int>> input(n, vector<int>(n, 0));
    for(int i=0;i<n;i++){
        for(int j=0;j<=i;j++)
            cin>>input[i][j];
    }
    cout<<maximumPathSumInTriangle(input);
}

}
3
1
2 3
5 8 1
12

ত্রিভুজটিতে সর্বাধিক পাথের যোগফল খুঁজতে জাভা কোড

import java.util.*;

class Main{
  static int maximumPathSumInTriangle(int input[][], int n)
  {
      // start from row above bottom row
      // since the bottom row cells are the answers themselves
    for(int i=n-2;i>=0;i--)
    {
        // start from left to right in column
      for(int j=0;j<=i;j++)
      {
        if(input[i+1][j] > input[i+1][j+1])
          input[i][j] += input[i+1][j];
        else
          input[i][j] += input[i+1][j+1];
      }
    }
    return input[0][0];
  }

  public static void main(String[] args)
  {
    Scanner sc = new Scanner(System.in);
      int n = sc.nextInt(); // number of rows
      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();
      }
      int answer = maximumPathSumInTriangle(input, n);
      System.out.print(answer);
  }
}
3
1
2 3
5 8 1
12

জটিলতা বিশ্লেষণ

সময় জটিলতা

ও (এন ^ 2), যেমন আমরা প্রতিটি সারি এবং প্রতিটি কলাম জুড়ে চলেছি। প্রক্রিয়াটিতে, আমরা প্রতিটি কক্ষে ভ্রমণ করেছি। এবং যেহেতু ত্রিভুজটিতে ও (এন ^ 2) কোষ ছিল এবং ডিপির পরিবর্তনে কেবল ও (1) অপারেশন লেগেছিল। সুতরাং, সময়ের জটিলতাও বহুপদী।

স্পেস জটিলতা ity

ও (এন ^ 2) যেহেতু আমরা একটি 2D ডিপি অ্যারে তৈরি করেছি। সুতরাং স্থান জটিলতাও বহুপদী।