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


വൈഷമ്യ നില മീഡിയം
പതിവായി ചോദിക്കുന്നു ക്സെൻ ഡി.ഇ.ഷാ ഡയറക്റ്റി ബൈ
ഡൈനാമിക് പ്രോഗ്രാമിംഗ് മഠം

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

ഉദാഹരണം  

ഒരു വലത് നമ്പർ ത്രികോണത്തിലെ ഒരു പാതയുടെ പരമാവധി തുകമൊട്ടുസൂചി

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

വിശദീകരണം

മുകളിൽ നിന്ന് താഴേക്ക് നീങ്ങുന്നതിലൂടെ നേടാനാകുന്ന പരമാവധി തുക 15 ആണ്. ഇനിപ്പറയുന്ന ഘട്ടങ്ങളിൽ നിന്ന് ഇത് നേടാൻ കഴിയും: 1 -> 2 -> 12. മുകളിലുള്ള ചിത്രത്തിൽ നിന്ന് ഇത് നന്നായി മനസ്സിലാക്കാൻ കഴിയും.

സമീപനം  

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

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

ഇതും കാണുക
ഒരു അറേയിലെ അടുത്തുള്ള ഘടകങ്ങൾ വേർതിരിക്കുക

പ്രാരംഭ ഇൻപുട്ട് അറേയുടെ സെല്ലിൽ ഡിപി [0] [0] പൂരിപ്പിക്കുന്നതുപോലെ ഞങ്ങൾ അടിസ്ഥാന കേസ് നിർവചിക്കുന്നു. കാരണം മറ്റേതൊരു സെല്ലിൽ നിന്നും ഞങ്ങൾക്ക് ഈ സെല്ലിൽ എത്താൻ കഴിയില്ല, ഇതാണ് ആരംഭം. ഇതിനുശേഷം, ഞങ്ങൾ രണ്ടാമത്തെ വരിയിലേക്ക് പോകുന്നു. ഇവിടെ നമുക്ക് രണ്ട് സെല്ലുകൾക്കും ഒരൊറ്റ ഓപ്ഷൻ ഉണ്ട്. മുകളിലെ വെർട്ടെക്സ് സെൽ തിരഞ്ഞെടുക്കുക എന്നതാണ് ഓപ്ഷൻ. ഈ വരിയ്ക്ക് ശേഷം, എല്ലാ സെല്ലുകൾക്കും ഏത് സെല്ലാണ് തിരഞ്ഞെടുക്കേണ്ടതെന്ന് ഞങ്ങൾ തീരുമാനിക്കേണ്ടതുണ്ട്, അത് സെല്ലിലേക്കുള്ള നീളം അല്ലെങ്കിൽ നിലവിലെ സെല്ലിന്റെ ഇടതുവശത്തുള്ള സെൽ. ഇതെല്ലാം ചെയ്തുകഴിഞ്ഞാൽ, dp പട്ടികയുടെ അവസാന വരിയിൽ സംഭരിച്ചിരിക്കുന്ന പരമാവധി എടുക്കും.

കോഡ്  

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

#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

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

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

O (N ^ 2), ഇവിടെ N എന്നത് ത്രികോണത്തിലെ വരികളുടെ എണ്ണത്തെ സൂചിപ്പിക്കുന്നു. കാരണം അവസാന വരിയിലുള്ള ഘടകങ്ങളുടെ എണ്ണം അതാണ്.

ഇതും കാണുക
ഏറ്റവും വലിയ ഹരിക്കാവുന്ന ജോഡി ഉപസെറ്റ്

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

O (1), കാരണം ഞങ്ങൾ ഡിപി പട്ടികയ്‌ക്കായി സമാന ഇൻപുട്ട് അറേ ഉപയോഗിക്കുന്നു. അതിനാൽ ഒരു പുതിയ ഡിപി അറേ സൃഷ്ടിക്കുന്നതിന് ഞങ്ങൾ സ്ഥലം എടുക്കാത്തതിനാൽ സ്ഥല സങ്കീർണ്ണത സ്ഥിരമാണ്.