ผลรวมเส้นทางตกน้อยที่สุด II ใน C++

คำอธิบายโจทย์

กริดสี่เหลี่ยม เลือก 1 ตัวต่อแถว ต้องไม่ใช่คอลัมน์เดียวกับแถวติดกัน หาผลรวมน้อยที่สุด

ตัวอย่าง

arr = [[1,2,3],[4,5,6],[7,8,9]] → Output: 13

เส้นทาง [1,5,7] = 13 (แถว0คอลัมน์0, แถว1คอลัมน์1, แถว2คอลัมน์0)

วิธีแก้ปัญหา

DP แบบ Bottom-up พร้อม optimization:

• แถว i ใช้ค่าจากแถว i-1
• คำนวณ leftMin[j] = min(arr[i-1][0..j])
• คำนวณ rightMin[j] = min(arr[i-1][j..m-1])
• arr[i][j] += min(leftMin[j-1], rightMin[j+1]) (ข้ามคอลัมน์เดียวกัน)
• คำตอบ = min ของแถวสุดท้าย

Time: O(n×m), Space: O(m)

การทำงานของโค้ด

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int minFallingPathSum(vector<vector<int>>& arr) {
        int n = arr.size(), m = arr[0].size();
        for(int i=1; i=0; j--) rightMin[j] = min(arr[i-1][j], rightMin[j+1]);
            
            for(int j=0; j=0) ? leftMin[j-1] : 1000000;
                int rightVal = (j+1

อินพุต
{{1,2,3},{4,5,6},{7,8,9}}

เอาต์พุต
13