תיאור השאלה
Given an m x n grid filled with non-negative numbers, find a path from the top-left cell to the bottom-right cell that minimizes the sum of the numbers along the path.
- You can only move either down or right at any point.
איך פותרים?
תכנון דינמי: העלות המינימלית להגיע לכל תא היא הערך שלו ועוד המינימום בין התא שמעליו לתא שמשמאלו. ממלאים שורה אחרי שורה, ומספיק מערך של שורה אחת. סיבוכיות: O(m·n).
פתרון קוד
JavaScript
Python
function minPathSum(grid) {
const m = grid.length;
const n = grid[0].length;
const dp = new Array(n).fill(Infinity);
dp[0] = 0;
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
const fromLeft = j > 0 ? dp[j - 1] : Infinity;
dp[j] = grid[i][j] + Math.min(dp[j], fromLeft);
}
}
return dp[n - 1];
}
לעבור את ראיון העבודה הבא שלך בהצלחה
קורס דיגיטלי מקיף עם +25 שיעורים מעשיים, כשעתיים של וידאו, וליווי של מראיין בכיר.