Гурвалжин дахь хамгийн бага нийлбэр зам


Хэцүү байдлын түвшин Дунд
Байнга асуудаг Амазоны 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

Гурвалжин дахь хамгийн бага замын нийлбэрийг олох 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 массивыг үүсгэсэн. Тиймээс орон зайн нарийн төвөгтэй байдал нь бас олон гишүүнт юм.