Максімальная сума шляху ў трохвугольніку з прамым лікам


Узровень складанасці серада
Часта пытаюцца ў Citrix DE Шоу Дырэкты 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.