Үшбұрыштың минималды қосындысы


Күрделілік дәрежесі орта
Жиі кіреді Amazon алма 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

Үшбұрыштағы минималды жол қосындысын табу үшін Java коды

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 массивін құрдық. Сонымен кеңістіктің күрделілігі де көпмүшелікке ие болады.