በሶስት ማዕዘን ውስጥ ከፍተኛው የመንገድ ድምር  


የችግር ደረጃ መካከለኛ
ውስጥ በተደጋጋሚ ተጠየቀ አርሴሲየም የኮድ ቁጥር GE የጤና PayU በ Uber ቮሆ
ተለዋዋጭ ፕሮግራም

የችግሩ መግለጫ  

ችግሩ “በሦስት ማዕዘኑ ውስጥ ያለው ከፍተኛው የመንገድ ድምር” አንዳንድ ቁጥሮች ይሰጥዎታል ይላል። እነዚህ ኢንቲጀሮች በሶስት ማዕዘን ቅርፅ የተደረደሩ ናቸው ፡፡ ከሶስት ማዕዘኑ አናት ጀምሮ ነው ወደ ታችኛው ረድፍ መድረስ ያስፈልግዎታል ፡፡ ይህንን ለማድረግ በሚቀጥለው ረድፍ ላይ ወደ ተጎራባች ህዋሶች ይዛወራሉ ፡፡ ስለዚህ በተገለጸው መንገድ የሶስት ማዕዘኑን ወደታች ሲወርዱ ሊያገኙት የሚችሉት ከፍተኛ ድምር ምንድነው?

ለምሳሌ  

በሶስት ማዕዘን ውስጥ ከፍተኛው የመንገድ ድምር

  1
 2 3
5 8 1
12

ማስረጃ
በሚከተለው መንገድ በቀላሉ መንገዱን ወደታች መሄድ ይችላሉ። 1-> 3-> 8 ፣ ይህ መንገድ ከፍተኛውን ድምር 12 እንዲያገኙ ያደርግዎታል ፡፡

ቀረበ  

ስለዚህ በሦስት ማዕዘኑ ውስጥ ከፍተኛውን የመንገድ ድምር እንዴት እንፈታዋለን? እስከዚህ ጊዜ ድረስ እንደነዚህ ዓይነቶቹን ችግሮች በደንብ እናውቃለን ፡፡ መቼም እንደዚህ አይነት ችግሮች ሲሰጡን ፡፡ የጭካኔ ኃይል አቀራረብ ሁልጊዜ መድረሻዎ ላይ ለመድረስ ሁሉንም ሊሆኑ የሚችሉ መንገዶችን በመጀመሪያ ማመንጨት ነው ፡፡ እና ከዚያ ለእያንዳንዱ መንገድ ድምርን በማስላት ለተመቻቸ ውጤት መልሱን ማዘመንዎን ይቀጥሉ። ግን ይህ አካሄድ መንገዶቹን እንድናመነጭ ስለሚፈልግ ይህ አካሄድ በጣም ውጤታማ አይደለም ፡፡ እና የጎዳና ትውልድ ጥሩ ያልሆነ የብልጭታ የጊዜ ውስብስብነት ያለው ተግባር መሆኑን እናውቃለን።

ስለዚህ ይህንን ለመፍታት ሌላ አካሄድ ማሰብ አለብን ፡፡ ከዚያ ተለዋዋጭ ፕሮግራም ወደ እኛ ለማዳን ይመጣል ፡፡ ምክንያቱም መንገዶቹን ከማመንጨት ይልቅ ወደ ታችኛው ረድፍ ለመድረስ ከሴል ማግኘት የሚቻለው ከፍተኛው ነገር ምን እንደሆነ በሆነ መንገድ ማወቅ ከቻልን ፡፡ በዚያ መንገድ ከጎኑ ያለው ህዋስ ውጤቱን ማግኘት እንችላለን ፣ ግን ከላይ ባለው ረድፍ ላይ። ስለዚህ ዲፒን ትናንሽ ንዑስ ችግሮችን ለመፍታት እንጠቀማለን ፡፡ ከዚያ ለእነዚያ ንዑስ ችግሮች ውጤቶችን በማጣመር ለዋናው ችግር መልስ እናገኛለን ፡፡

ተመልከት
የክፍል ዛፍ

በመጀመሪያ በመጨረሻው ረድፍ ላይ ለሚገኙት ህዋሶች መልሱን እንሞላለን ፡፡ በታችኛው ረድፍ ላይ ካሉ ህዋሳት ከጀመርን ሊደረስበት የሚችል ከፍተኛው ድምር ቁጥሩ ራሱ መሆኑን እናውቃለን ፡፡ ከዚያ በኋላ ከታችኛው ረድፍ በላይ ወዳለው ረድፍ እንሄዳለን ፡፡ አሁን ባለው ረድፍ ውስጥ ላለው እያንዳንዱ ሕዋስ ፣ ከሱ በታች ባለው ረድፍ ላይ በአጠገብ የሚገኙትን የሴሎች ዲፒ እሴቶችን መምረጥ እንችላለን ፡፡ በዚህ መንገድ ወደ ላይ አቅጣጫ መሄዳችንን እንቀጥላለን። ወደ ላይኛው ረድፍ እንደደረስን ከችግሩ ጋር ጨርሰናል ፡፡

በሦስት ማዕዘኑ ውስጥ ከፍተኛውን የመንገድ ድምርን ለማግኘት የ C ++ ኮድ  

#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

ውስብስብነት ትንተና  

የጊዜ ውስብስብነት

ኦ (N ^ 2)፣ በእያንዳንዱ ረድፍ እና በእያንዳንዱ አምድ ላይ ስናልፍ ፡፡ በሂደቱ ውስጥ ወደ እያንዳንዱ ሕዋስ ተጓዝን ፡፡ እናም በሦስት ማዕዘኑ ውስጥ ኦ (N ^ 2) ሕዋሶች ስለነበሩ እና ለዲፒ የሚደረግ ሽግግር የ O (1) ሥራን ብቻ ወስዷል ፡፡ ስለዚህ ፣ የጊዜ ውስብስብነትም እንዲሁ ፖሊኖሚያል ነው።

ተመልከት
Palindrome የተገናኘ ዝርዝር Leetcode መፍትሔ

የቦታ ውስብስብነት

ኦ (N ^ 2) የ 2 ዲ ዲፒ ድርድር ስለፈጠርን ፡፡ ስለዚህ የቦታ ውስብስብነት እንዲሁ ፖሊኖሚያል ነው።