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


Күрделілік дәрежесі орта
Жиі кіреді Citrix DE Шоу Directi Expedia
Динамикалық бағдарламалау математика

«Тік бұрышты үшбұрыштағы жолдың максималды қосындысы» деген есеп сізге бірнеше берілгенін айтады бүтін сандар тік бұрышты үшбұрыш түрінде. Егер сіз жоғарыдан бастағанда және оның астындағы ұяшыққа немесе оның оң жағындағы бір орынға жылжитын етіп негізге қарай жылжысаңыз, қол жеткізе алатын ең үлкен соманы біліңіз.

мысал  

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

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

Түсіндіру

Жоғарыдан төменге жылжу арқылы қол жеткізуге болатын максималды қосынды 15. Бұған келесі қадамдардан қол жеткізуге болады: 1 -> 2 -> 12. Оны жоғарыдағы кескіннен жақсы түсінуге болады.

жақындау  

Бізде осы проблемаға ұқсас басқа проблемалар бар. Біз проблемаларды шештік максимум, минимум үшбұрыштағы қосынды жол. Бұл проблема - сол мәселелердің шамалы өзгеруі. Сонымен, қозғалысқа қойылатын шарт - сіз қазіргі ұяшықтың дәл астында немесе дәл жүре аласыз. Сіз жоғарғы шыңнан басталатын жоғарыдан бастаңыз. Содан кейін түбіне жетіңіз.

Бір тәсілі - пайдалану рекурсия. Біз индекстерді аргумент ретінде қабылдайтын және осы ұяшықтан максимумға жететін функцияны құрамыз. Осылайша біз жауапты рекурсивті түрде табамыз. Бірақ бұл проблеманы көп уақытты қажет етеді және уақыттың шегінен асып кетуіне әкеледі. Мәселен, мәселені тиімді шешу. Біз осы рекурсивті қоңыраулардың нәтижесін жаттай аламыз. Немесе пайдаланыңыз Динамикалық бағдарламалау мұны шешу. Алдымен кіші есептердің нәтижесін есептейтін, содан кейін нәтижелерді біріктіріп, бастапқы есептің жауабын табатын «төменнен жоғарыға» әдісті талқылаймыз.

Сондай-ақ, қараңыз
Массивтегі айқын іргелес элементтер

DP [0] [0] бастапқы жиым ұяшығымен толтырылатын негізгі жағдайды анықтаймыз. Себебі біз бұл ұяшыққа басқа ұяшықтардан жете алмаймыз және бұл бастама. осыдан кейін біз екінші қатарға шығамыз. мұнда бізде екі ұяшыққа арналған жалғыз нұсқа бар. және опция жоғарғы шың ұяшығын таңдау болып табылады. Осы жолдан кейін барлық ұяшықтар үшін қай ұяшықты тек ұяшыққа немесе ағымдағы ұяшықтың сол жағында орналасқан ұяшыққа таңдау керек екенін шешу керек. Мұның бәрі аяқталғаннан кейін, біз dp кестесінің соңғы жолында сақталған максимумды аламыз.

код  

Оң жақ үшбұрыштағы жолдың максималды қосындысын табуға арналған C ++ коды

#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

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

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

Күрделілікті талдау  

Уақыттың күрделілігі

O (N ^ 2), Мұндағы N үшбұрыштағы жолдар санына жатады. Себебі бұл соңғы қатарда тұрған элементтер саны.

Сондай-ақ, қараңыз
Бөлінетін ең үлкен жұп жиын

Ғарыштың күрделілігі

O (1), өйткені біз DP кестесі үшін бірдей енгізу массивін қолданамыз. Осылайша, кеңістіктің күрделілігі тұрақты, өйткені біз жаңа DP массивін құруға орын алмадық.