ഒരു ത്രികോണത്തിലെ പരമാവധി പാത്ത് തുക


വൈഷമ്യ നില മീഡിയം
പതിവായി ചോദിക്കുന്നു ആർസെസിയം കോഡ്നേഷൻ GE ഹെൽത്ത്കെയർ പേ യൂബർ Zoho
ഡൈനാമിക് പ്രോഗ്രാമിംഗ്

പ്രശ്നം പ്രസ്താവന

“ഒരു ത്രികോണത്തിലെ പരമാവധി പാത്ത് തുക” എന്ന പ്രശ്നം നിങ്ങൾക്ക് ചില സംഖ്യകൾ നൽകിയിട്ടുണ്ടെന്ന് പറയുന്നു. ഈ സംഖ്യകൾ ഒരു ത്രികോണത്തിന്റെ രൂപത്തിലാണ് ക്രമീകരിച്ചിരിക്കുന്നത്. നിങ്ങൾ ത്രികോണത്തിന്റെ മുകളിൽ നിന്ന് ആരംഭിക്കുകയും താഴത്തെ വരിയിലെത്തുകയും വേണം. ഇത് ചെയ്യുന്നതിന്, നിങ്ങൾ അടുത്ത വരിയിലെ അടുത്തുള്ള സെല്ലുകളിലേക്ക് നീങ്ങുന്നു. അതിനാൽ നിങ്ങൾ നിർവചിക്കപ്പെട്ട രീതിയിൽ ത്രികോണത്തിലേക്ക് നീങ്ങുമ്പോൾ, നിങ്ങൾക്ക് നേടാൻ കഴിയുന്ന പരമാവധി തുക എത്രയാണ്?

ഉദാഹരണം

ഒരു ത്രികോണത്തിലെ പരമാവധി പാത്ത് തുക

  1
 2 3
5 8 1
12

വിശദീകരണം
ഇനിപ്പറയുന്ന രീതിയിൽ നിങ്ങൾക്ക് പാതയിലേക്ക് നീങ്ങാം. 1-> 3-> 8, ഈ പാത നിങ്ങളെ പരമാവധി 12 ആകാൻ സഹായിക്കും.

സമീപനം

ഒരു ത്രികോണത്തിലെ പരമാവധി പാത്ത് തുക എങ്ങനെ പരിഹരിക്കും? ഇപ്പോൾ വരെ, ഇത്തരത്തിലുള്ള പ്രശ്‌നങ്ങളെക്കുറിച്ച് ഞങ്ങൾക്ക് നല്ല പരിചയമുണ്ട്. ഞങ്ങൾക്ക് ഇത്തരം പ്രശ്നങ്ങൾ നൽകുമ്പോഴെല്ലാം. നിങ്ങളുടെ ലക്ഷ്യസ്ഥാനത്ത് എത്താൻ സാധ്യമായ എല്ലാ വഴികളും ആദ്യം സൃഷ്ടിക്കുക എന്നതാണ് എല്ലായ്പ്പോഴും ബ്രൂട്ട് ഫോഴ്‌സ് സമീപനം. ഓരോ പാതയുടെയും തുക കണക്കാക്കിക്കൊണ്ട് ഒപ്റ്റിമൽ ഫലത്തിനുള്ള ഉത്തരം അപ്‌ഡേറ്റ് ചെയ്യുന്നത് തുടരുക. എന്നാൽ ഈ സമീപനം വളരെ കാര്യക്ഷമമല്ലാത്തതിനാൽ ഈ സമീപനം ഞങ്ങൾക്ക് പാതകൾ സൃഷ്ടിക്കാൻ ആവശ്യപ്പെടുന്നു. എക്‌സ്‌പോണൻഷ്യൽ സമയ സങ്കീർണ്ണത നല്ലതല്ലാത്ത ഒരു ജോലിയാണ് പാത്ത് ജനറേഷൻ എന്ന് നമുക്കറിയാം.

അതിനാൽ, ഇത് പരിഹരിക്കാൻ മറ്റൊരു സമീപനത്തെക്കുറിച്ച് ചിന്തിക്കേണ്ടതുണ്ട്. പിന്നെ ഡൈനാമിക് പ്രോഗ്രാമിംഗ് ഞങ്ങളുടെ രക്ഷയ്‌ക്കെത്തുന്നു. കാരണം, പാതകൾ സൃഷ്ടിക്കുന്നതിനുപകരം, ഒരു സെല്ലിൽ നിന്ന് താഴത്തെ വരിയിലെത്താൻ കഴിയുന്ന പരമാവധി തുക എന്താണെന്ന് നമുക്ക് എങ്ങനെയെങ്കിലും അറിയാൻ കഴിയുമെങ്കിൽ. അതുവഴി സെല്ലിനോട് ചേർന്നുള്ളതും എന്നാൽ അതിന് മുകളിലുള്ള വരിയിലുള്ളതുമായ ഫലം നമുക്ക് ലഭിക്കും. അതിനാൽ, ചെറിയ ഉപപ്രശ്നങ്ങൾ പരിഹരിക്കാൻ ഞങ്ങൾ ഡിപി ഉപയോഗിക്കുന്നു. ആ ഉപപ്രശ്നങ്ങൾക്കുള്ള ഫലങ്ങൾ സംയോജിപ്പിച്ച് യഥാർത്ഥ പ്രശ്‌നത്തിനുള്ള ഉത്തരങ്ങൾ ഞങ്ങൾ കണ്ടെത്തുന്നു.

ആദ്യം, അവസാന വരിയിലെ സെല്ലുകൾക്കുള്ള ഉത്തരം ഞങ്ങൾ പൂരിപ്പിക്കുന്നു. ചുവടെയുള്ള വരിയിലെ സെല്ലുകളിൽ നിന്ന് ആരംഭിക്കുകയാണെങ്കിൽ നേടാനാകുന്ന പരമാവധി തുക സംഖ്യയാണെന്ന് നമുക്കറിയാം. അതിനുശേഷം, ഞങ്ങൾ താഴത്തെ വരിയുടെ മുകളിലുള്ള വരിയിലേക്ക് നീങ്ങുന്നു. നിലവിലെ വരിയിലെ ഓരോ സെല്ലിനും, അതിനു തൊട്ടുതാഴെയുള്ള വരിയിലെ സെല്ലുകളുടെ ഡിപി മൂല്യങ്ങൾ നമുക്ക് തിരഞ്ഞെടുക്കാം. ഇതുവഴി ഞങ്ങൾ മുകളിലേക്കുള്ള ദിശയിൽ തുടരുന്നു. മുകളിലെ വരിയിൽ എത്തുമ്പോൾ, ഞങ്ങൾ പ്രശ്‌നം പൂർത്തിയാക്കി.

ഒരു ത്രികോണത്തിലെ പരമാവധി പാത്ത് തുക കണ്ടെത്തുന്നതിന് സി ++ കോഡ്

#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

സങ്കീർണ്ണത വിശകലനം

സമയ സങ്കീർണ്ണത

O (N ^ 2), ഓരോ വരിയിലും ഓരോ നിരയിലും ഞങ്ങൾ നീങ്ങുമ്പോൾ. പ്രക്രിയയിൽ, ഞങ്ങൾ ഓരോ സെല്ലിലേക്കും യാത്ര ചെയ്തു. ത്രികോണത്തിൽ O (N ^ 2) സെല്ലുകൾ ഉള്ളതിനാൽ ഡിപിയുടെ പരിവർത്തനം O (1) പ്രവർത്തനം മാത്രമേ എടുത്തിട്ടുള്ളൂ. അതിനാൽ, സമയ സങ്കീർണ്ണതയും പോളിനോമിയലാണ്.

ബഹിരാകാശ സങ്കീർണ്ണത

O (N ^ 2) ഞങ്ങൾ ഒരു 2D ഡിപി അറേ സൃഷ്ടിച്ചതിനാൽ. അതിനാൽ ബഹിരാകാശ സങ്കീർണ്ണതയും പോളിനോമിയൽ ആണ്.