Үч бурчтуктагы минималдуу сумма жолу


Кыйынчылык деңгээли орто
Көп суралган Amazon алма Bloomberg
согуштук тизме Динамикалык программалоо

Маселени билдирүү

“Үч бурчтуктагы минималдуу суммалык жол” маселеси сизге бүтүн сандардын үч бурчтугу түрүндөгү ырааттуулук берилгенин билдирет. Эми жогорку саптан баштап, төмөнкү сапка жеткенде канча суммага жете аласыз?

мисал

Үч бурчтуктагы минималдуу сумма жолу

  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 массивин түздүк. Ошентип, мейкиндиктин татаалдыгы да көп мүчөлүү.