Düz nömrəli üçbucaqdakı yolun maksimum cəmi

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Citrix DE Şou Directi Expedia
Dinamik proqramlaşdırma RiyaziyyatBaxılıb 61

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.

"Düz nömrəli üçbucaqdakı yolun maksimum cəmi" problemi sizə bir neçəsinin verildiyini bildirir tamsayılar düz ədəd üçbucağı şəklində. Yuxarıdan başlayaraq bazaya doğru hərəkət etsəniz, əldə edə biləcəyiniz maksimum məbləği yalnız altındakı hüceyrəyə və ya onun sağındakı bir yerə keçin.

misal

Düz nömrəli üçbucaqdakı yolun maksimum cəmiPin

3 // Number of rows in the right number triangle
1
3 2
4 10 12
15

Izahat

Yuxarıdan aşağıya doğru hərəkət etməklə əldə edilə bilən maksimum məbləğ 15. Bu, aşağıdakı addımlardan əldə edilə bilər: 1 -> 2 -> 12. Yuxarıdakı görüntüdən daha yaxşı başa düşülə bilər.

Yanaşma

Artıq bu problemə bənzər digər problemlərimiz var. Tapmaq üçün problemləri həll etdik maksimum, minimum üçbucaqdakı cəmi yol. Bu problem bu problemlərin bir az dəyişməsidir. Beləliklə, hərəkətə qoyulan şərt, mövcud hücrənin dərhal altına və ya düzünə getməkdir. Və yuxarı zirvədən olan yuxarıdan başlayırsınız. Sonra altına çat.

Bir yolu istifadə etməkdir rekursiya. İndeksləri arqument kimi qəbul edəcək və bu hücrədən əldə edilə bilən maksimumu tapacaq bir funksiya yaradacağıq. Bu şəkildə cavabı rekursiv şəkildə tapırıq. Ancaq bu problemi çox vaxt aparır və şübhəsiz ki, vaxt həddini aşmaqla nəticələnəcəkdir. Beləliklə problemi səmərəli həll etmək. Bu rekursiv zənglərin nəticəsini ya əzbərləyə bilərik. Və ya istifadə edin Dinamik proqramlaşdırma bunu həll etmək. Əvvəlcə nəticəni daha kiçik alt problemlər üçün hesablayacaq və sonra bu nəticələri birləşdirərək orijinal problemin cavabını tapacaq bir aşağıdan yuxarı yanaşmanı müzakirə edəcəyik.

DP [0] [0] -ni ilkin giriş massivinin xanası ilə doldurmaq kimi əsas vəziyyəti təyin edirik. Çünki başqa bir hücrədən bu hüceyrəyə çata bilmərik və bu başlanğıcdır. bundan sonra ikinci sıraya gedirik. burada hər iki hüceyrə üçün tək bir seçimimiz var. və seçim yuxarıda vertex hüceyrəsini seçməkdir. Sonra bu sətirdən sonra, bütün hüceyrələr üçün hansı hücrəni yalnız hücrəyə və ya cari hücrənin yalnız solundakı hüceyrəni seçəcəyinə qərar verməyimiz lazımdır. Bütün bunlardan sonra dp cədvəlinin sonuncu sətrində saxlanılan maksimumu alırıq.

Kodu

Düz nömrəli üçbucaqdakı yolun maksimum cəmini tapmaq üçün C ++ kodu

#include<bits/stdc++.h>
using namespace std;

int main(){
    int n;cin>>n;
    int input[n][n];
    for(int i=0;i<n;i++)
        for(int j=0;j<=i;j++)
            cin>>input[i][j];
  if (n > 1)
    input[1][1] = input[1][1] + input[0][0];
    input[1][0] = input[1][0] + input[0][0];
  for(int i = 2; i < n; i++){
        // because the boundary cells have only a single option
    input[i][0] = input[i][0] + input[i-1][0];
    input[i][i] = input[i][i] + input[i-1][i-1];
    for (int j = 1; j < i; j++)
            input[i][j] = input[i][j] + max(input[i-1][j-1], input[i-1][j]);
  }

  int ans = INT_MIN;
  for(int i=0;i<n;i++)
        ans = max(ans, input[n-1][i]);
  cout<<ans;
}
3
1
3 2
4 10 12
15

Düz nömrəli üçbucaqdakı yolun maksimum cəmini tapmaq üçün Java kodu

import java.util.*;
class Main{
  public static void main(String[] args)
  {
    Scanner sc = new Scanner(System.in);
      int n = sc.nextInt();
      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();;
    if (n > 1)
      input[1][1] = input[1][1] + input[0][0];
      input[1][0] = input[1][0] + input[0][0];
    for(int i = 2; i < n; i++){
          // because the boundary cells have only a single option
      input[i][0] = input[i][0] + input[i-1][0];
      input[i][i] = input[i][i] + input[i-1][i-1];
      for (int j = 1; j < i; j++)
              input[i][j] = input[i][j] + Math.max(input[i-1][j-1], input[i-1][j]);
    }

    int ans = Integer.MIN_VALUE;
    for(int i=0;i<n;i++)
          ans = Math.max(ans, input[n-1][i]);
    System.out.println(ans);
  }
}
3
1
3 2
4 10 12
15

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi

O (N ^ 2), burada N üçbucaqdakı sıra sayına aiddir. Çünki bu, son sıradakı elementlərin sayıdır.

Kosmik Mürəkkəblik

O (1), çünki DP cədvəli üçün eyni giriş massivini istifadə edirik. Beləliklə, kosmik mürəkkəblik sabitdir, çünki yeni bir DP seriyası yaratmaq üçün yer almamışıq.

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