ปัญหา
เลือก 1 element ต่อ row ไม่ให้ติดคอลัมน์กันระหว่างแถวติดกัน หา path ที่ sum น้อยที่สุด
ตัวอย่าง
matrix = [[4,7,1],[2,8,3],[5,6,9]] valid paths และ sums: [4,8,9]=21, [4,8,6]=18, [4,3,6]=13, [4,3,5]=12 [7,2,6]=15, [7,2,9]=18, [7,3,6]=16, [7,3,5]=15 [1,2,6]=9, [1,2,9]=12, [1,8,9]=18, [1,8,5]=14 min = 9 (path [1,2,6])
ตัวอย่างโค้ด
const arr = [
[4, 7, 1],
[2, 8, 3],
[5, 6, 9]
];
const minimumPathSum = (arr = []) => {
let first = [0, null];
let second = [0, null];
for (let row = arr.length - 1; row >= 0; row--) {
let curr1 = null;
let curr2 = null;
for (let column = 0; column < arr[row].length; column++) {
let currentSum = arr[row][column];
if (column !== first[1]) {
currentSum += first[0];
} else {
currentSum += second[0];
}
if (curr1 === null || currentSum < curr1[0]) {
curr2 = curr1;
curr1 = [currentSum, column];
} else if (curr2 === null || currentSum < curr2[0]) {
curr2 = [currentSum, column];
}
}
first = curr1;
second = curr2;
}
return first[0];
};
console.log(minimumPathSum(arr));
ผลลัพธ์
9
คำอธิบาย
Bottom-up DP: เก็บ first (min sum) และ second (2nd min sum) ของ row ถัดไป พร้อม column
สำหรับแต่ละ column ใน row ปัจจุบัน: ห้ามใช้ column เดียวกับ first -> ใช้ second แทน
อัปเดต first/second ใหม่สำหรับ row นี้
Time: O(m*n), Space: O(1)
