נתיב סכום מינימלי במשולש


רמת קושי בינוני
נשאל לעתים קרובות אמזון בעברית תפוח עץ בלומברג
מערך תכנות דינמי

הצהרת בעיה

הבעיה "נתיב סכום מינימלי במשולש" קובעת שאתה מקבל רצף בצורה של משולש של מספרים שלמים. כעת החל מהשורה העליונה מה הסכום המינימלי שתוכל להשיג כאשר תגיע לשורה התחתונה?

דוגמה

נתיב סכום מינימלי במשולש

  1
 2 3
5 8 1
5

הסבר
אתה יכול פשוט לעבור בדרך הבאה. 1-> 3-> 1. לפיכך הסכום הוא 5. אם היינו הולכים בגישה חמדנית. היינו הולכים עם 2 במקום 3. אז אנחנו יכולים להגיע רק ל 8 או 11 שהם גדולים מ 5.

גישה

אז איך נפתור את נתיב הסכום המינימלי במשולש? פתרנו גם בעיה דומה בה היינו צריכים למצוא את נתיב סכום מרבי במשולש. בפוסט הקודם ההוא כבר דנו כי גישת הכוח הגס לבעיות אלה היא לייצר את כל הנתיבים. לאחר יצירת הנתיבים הללו, פשוט חישב את הסכום עבור כל אחד מהנתיבים האלה ועדכן את הסכום המינימלי.

אז במקום לפתור בעיה זו באמצעות כוח אכזרי, אנו פותרים זאת באמצעות תכנות דינמי. מכיוון שגישת כוח הברוט אינה יעילה ביותר.

ראשית, אנו ממלאים את התשובה עבור התאים בשורה האחרונה. אנו יודעים שהסכום המינימלי שניתן להשיג הוא אם נתחיל מהתאים בשורה התחתונה הוא המספר עצמו. לאחר מכן, אנו עוברים לשורה מעל השורה התחתונה. עבור כל תא בשורה הנוכחית, אנו יכולים לבחור את ערכי ה- DP של התאים הסמוכים אליו בשורה שמתחתיה. ומלא את הערך המינימלי שניתן להשיג. בדרך זו אנו ממשיכים בכיוון כלפי מעלה. כשאנחנו מגיעים לשורה העליונה, סיימנו עם הבעיה.

קוד C ++ למציאת סכום נתיב מינימלי במשולש

#include<bits/stdc++.h>
using namespace std;
int minimumPathSumInTriangle(vector<vector<int>> &input)
{
    int n = input.size();
    // start from row above bottom row
    // since the bottom row cells are the answers themselves
  for(int i=n-2;i>=0;i--)
  {
      // start from left to right in column
    for(int j=0;j<=i;j++)
    {
      if(input[i+1][j] < input[i+1][j+1])
        input[i][j] += input[i+1][j];
      else
        input[i][j] += input[i+1][j+1];
    }
  }
  return input[0][0];
}
int main()
{
    int n;cin>>n; // number of rows
    vector<vector<int>> input(n, vector<int>(n, 0));
    for(int i=0;i<n;i++){
        for(int j=0;j<=i;j++)
            cin>>input[i][j];
    }
    cout<<minimumPathSumInTriangle(input);
}
3
1
2 3
5 8 1
5

קוד Java כדי למצוא סכום נתיב מינימלי במשולש

import java.util.*;
class Main{
  static int minimumPathSumInTriangle(int input[][], int n)
  {
      // start from row above bottom row
      // since the bottom row cells are the answers themselves
    for(int i=n-2;i>=0;i--)
    {
        // start from left to right in column
      for(int j=0;j<=i;j++)
      {
        if(input[i+1][j] < input[i+1][j+1])
          input[i][j] += input[i+1][j];
        else
          input[i][j] += input[i+1][j+1];
      }
    }
    return input[0][0];
  }
  public static void main(String[] args)
  {
    Scanner sc = new Scanner(System.in);
      int n = sc.nextInt(); // number of rows
      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();
      }
      int answer = minimumPathSumInTriangle(input, n);
      System.out.print(answer);
  }
}
3
1
2 3
5 8 1
5

ניתוח מורכבות

מורכבות זמן

O (N ^ 2)כאשר עברנו בכל שורה ובכל עמודה. בתהליך נסענו לכל תא. ומכיוון שהיו תאי O (N ^ 2) במשולש והמעבר ל- DP לקח רק O (1). לפיכך, מורכבות הזמן היא גם פולינומית.

מורכבות בחלל

O (N ^ 2) מאז שיצרנו מערך DP דו-ממדי. לפיכך מורכבות החלל היא גם פולינומית.