סכום מקסימלי של נתיב במשולש מספר נכון


רמת קושי בינוני
נשאל לעתים קרובות Citrix דה שו דירקטי 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 חדש.