Ҷамъи максималии роҳ дар секунҷаи росткунҷа


Сатҳи душворӣ миёна
Аксар вақт пурсида мешавад 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 ба шумораи сатрҳои секунҷа ишора мекунад. Зеро ин шумораи унсурҳое мебошад, ки дар сафи охир мебошанд.

Мураккабии фазо

О (1), зеро мо барои массиви DP ҳамон массиви вурудро истифода мебарем. Ҳамин тариқ, мураккабии фазо доимӣ аст, зеро мо барои эҷоди массиви нави DP ҷой нагирифтем.