תיאור השאלה
Given a triangle array, return the minimum path sum from top to bottom. At each step you may move to one of the two adjacent numbers in the row below: from index i to index i or i + 1.
איך פותרים?
פותרים מלמטה למעלה: מתחילים מהשורה התחתונה, ולכל איבר בשורה שמעליה מוסיפים את המינימום מבין שני השכנים שמתחתיו. בסוף dp[0] הוא התשובה. כך אין מקרי קצה בצדדים. סיבוכיות: O(n²) זמן, O(n) זיכרון.
פתרון קוד
JavaScript
Python
function minimumTotal(triangle) {
const dp = [...triangle[triangle.length - 1]];
for (let i = triangle.length - 2; i >= 0; i--) {
for (let j = 0; j <= i; j++) {
dp[j] = triangle[i][j] + Math.min(dp[j], dp[j + 1]);
}
}
return dp[0];
}
לעבור את ראיון העבודה הבא שלך בהצלחה
קורס דיגיטלי מקיף עם +25 שיעורים מעשיים, כשעתיים של וידאו, וליווי של מראיין בכיר.