მინიმალური ჯამის გზა სამკუთხედში


Რთული ტური საშუალო
ხშირად ეკითხებიან Amazon Apple Bloomberg
Array დინამიური პროგრამირება

პრობლემის განცხადება

პრობლემა "მინიმალური ჯამის გზა სამკუთხედში" აცხადებს, რომ თქვენ გეძლევათ თანმიმდევრობა მთელი რიცხვების სამკუთხედის სახით. ახლა ზედა რიგიდან დაწყებული, რა არის მინიმალური თანხა, რომლის მიღწევაც შეგიძლიათ ქვედა მწკრივში?

მაგალითი

მინიმალური ჯამის გზა სამკუთხედში

  1
 2 3
5 8 1
5

განმარტება
შეგიძლიათ უბრალოდ გადაადგილდეთ ბილიკით შემდეგი გზით. 1-> 3-> 1. ამრიგად, ჯამია 5. თუ ხარბი მიდგომით წავიდოდით. ჩვენ 2-ის ნაცვლად 3-ით წავიდოდით. ​​ამრიგად, ჩვენ მხოლოდ 8-ით ან 11-ით შეიძლება მივიღოთ, რაც 5-ზე მეტია.

მიდგომა

ასე როგორ უნდა მოვაგვაროთ მინიმალური ჯამის გზა სამკუთხედში? ჩვენ ასევე გადავწყვიტეთ მსგავსი პრობლემა, სადაც უნდა აღმოგვეჩინა მაქსიმალური ჯამის გზა სამკუთხედში. წინა პოსტში ჩვენ უკვე განვიხილეთ, რომ უხეში ძალის მიდგომა ამ პრობლემების მიმართ არის ყველა ბილიკის წარმოქმნა. ამ ბილიკების წარმოქმნის შემდეგ, უბრალოდ გამოთვალეთ თანხა თითოეული ამ ბილიკისთვის და განაახლეთ მინიმალური თანხა.

ამ პრობლემის გადაჭრის ნაცვლად უხეში ძალის გამოყენებით, ჩვენ ამას ვაგვარებთ დინამიური პროგრამირება. რადგან უხეში ძალის მიდგომა ძალზე არაეფექტურია.

პირველი, ჩვენ შეავსებთ პასუხს ბოლო რიგის უჯრედებისათვის. ჩვენ ვიცით, რომ მინიმალური ჯამი, რომლის მიღწევაც შეიძლება, არის თუ ქვედა რიგის უჯრედებიდან დავიწყებთ, თვით რიცხვია. ამის შემდეგ, ჩვენ გადავდივართ მწკრივზე ქვედა რიგის ზემოთ. ამჟამინდელი სტრიქონის თითოეული უჯრისთვის ჩვენ შეგვიძლია ავირჩიოთ უჯრედების DP მნიშვნელობები, რომლებიც მასთან არის მიმდებარე რიგში, მის ქვემოთ. და შეავსეთ მინიმალური მნიშვნელობა, რომლის მიღწევაც შეიძლება. ამ გზით ჩვენ განვაგრძობთ აღმავალი მიმართულებით. ზედა მწკრივთან მისვლისთანავე დავასრულეთ პრობლემა.

C ++ კოდი სამკუთხედში მინიმალური გეზის ჯამის მოსაძებნად

#include<bits/stdc++.h>
using namespace std;
int minimumPathSumInTriangle(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<<minimumPathSumInTriangle(input);
}
3
1
2 3
5 8 1
5

ჯავის კოდი სამკუთხედში მინიმალური გეზის ჯამის მოსაძებნად

import java.util.*;
class Main{
  static int minimumPathSumInTriangle(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 = minimumPathSumInTriangle(input, n);
      System.out.print(answer);
  }
}
3
1
2 3
5 8 1
5

სირთულის ანალიზი

დროის სირთულე

O (N ^ 2), როგორც თითოეულ სტრიქონს და თითოეულ სვეტს გადავაადგილეთ. ამ პროცესში თითოეულ საკანში გავემგზავრეთ. და რადგან სამკუთხედში იყო O (N ^ 2) უჯრედი და DP– სთვის გადასვლამ მხოლოდ O (1) ოპერაცია მიიღო. ამრიგად, დროის სირთულე ასევე მრავალწევრია.

სივრცის სირთულე

O (N ^ 2) მას შემდეგ რაც შევქმენით 2D DP მასივი. ამრიგად, სივრცის სირთულე ასევე მრავალწევრია.