Üçbucaqdakı minimum cəm ​​yolu

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Amazon alma Bloomberg
Geyim Dinamik proqramlaşdırmaBaxılıb 78

Sistem dizaynı ilə bağlı müsahibə sualları o qədər açıq ola bilər ki, düzgün hazırlaşmağı bilmək çox çətindir. İndi satın aldıqdan sonra Amazon, Microsoft və Adobe-nin dizayn dövrlərini sındıra bilirəm Bu kitabı. Gündəlik bir yenidən nəzərdən keçirin dizayn sualı və söz verirəm ki, dizayn dövrünü sındıra bilərsiniz.

Problem bəyanat

“Üçbucaqdakı minimum cəm ​​yolu” problemi sizə tam ədədlər üçbucağı şəklində ardıcıllığın verildiyini bildirir. İndi yuxarı sıradan başlayaraq alt sıraya çatanda əldə edə biləcəyiniz minimum məbləğ nədir?

misal

Üçbucaqdakı minimum cəm ​​yoluPin

  1
 2 3
5 8 1
5

Izahat
Sadəcə olaraq aşağıdakı şəkildə yolda irəliləyə bilərsiniz. 1-> 3-> 1. Beləliklə cəmi 5.-dir, əgər acgöz bir yanaşma ilə getsəydik. 2 əvəzinə 3 ilə gedərdik. Beləliklə 8-dən böyük olan yalnız 11 və ya 5 ilə sona çatırıq.

Yanaşma

Bəs üçbucaqdakı Minimum cəm ​​yolunu necə həll edirik? Tapmalı olduğumuz oxşar bir problemi də həll etdik üçbucaqdakı maksimum cəm ​​yolu. Əvvəlki yazımızda, bu problemlər üçün kobud güc yanaşmasının bütün yolları yaratmaq olduğunu müzakirə etmişdik. Bu yolların yaranmasından sonra, yalnız bu yolların hər biri üçün cəmi hesablayın və minimum cəmi yeniləyin.

Beləliklə, bu problemi kobud gücdən istifadə etmək əvəzinə, ilə həll edirik dinamik proqramlaşdırma. Çünki kobud güc yanaşması olduqca səmərəsizdir.

Əvvəlcə son sıradakı hüceyrələrin cavabını doldururuq. Bilirik ki, əldə edilə bilən minimum məbləğ, alt sıradakı hüceyrələrdən başlayırıqsa, rəqəmin özüdür. Bundan sonra alt sıranın üstündəki sıraya keçirik. Mövcud cərgədəki hər bir hüceyrə üçün onun altındakı sətirdə ona bitişik olan hüceyrələrin DP dəyərlərini seçə bilərik. Və əldə edilə bilən minimum dəyəri doldurun. Bu yolla yuxarı istiqamətdə davam edirik. Üst sıraya çatdıqda problemi həll edirik.

Üçbucaqda minimum yol cəmini tapmaq üçün C ++ kodu

#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

Üçbucaqda minimum yol cəmini tapmaq üçün Java kodu

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

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi

O (N ^ 2), hər sətirdə və hər sütunda hərəkət etdikdə. Bu müddət ərzində hər hücrəyə getdik. Üçbucaqda O (N ^ 2) hüceyrələri olduğundan və DP üçün keçid yalnız O (1) əməliyyatını aldı. Beləliklə, zamanın mürəkkəbliyi çox polinomdur.

Kosmik Mürəkkəblik

O (N ^ 2) 2D DP dizisi yaratdığımız üçün. Beləliklə, kosmik mürəkkəblik də polinomdur.

Crack Sistemi Dizayn Müsahibələri
Translate »