Максимальна сума шляху в трикутнику прямого числа


Рівень складності Medium
Часто запитують у Citrix Д. Е. Шоу 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.

код

Код С ++, щоб знайти максимальну суму шляху в трикутнику з правильним числом

#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.