home

หน้าแรก
 Computer >> บทช่วยสอนคอมพิวเตอร์ >  >> การเขียนโปรแกรม >> C++

Minimum Falling Path Sum ใน C++: หาเส้นทางผลรวมน้อยที่สุดในเมทริกซ์

โจทย์

เมทริกซ์ n×n หา falling path sum น้อยที่สุด: เริ่มแถวแรกคอลัมน์ไหนก็ได้ เลือก 1 ตัวต่อแถว คอลัมน์ถัดไปต่างได้ ≤ 1

ตัวอย่าง: [[1,2,3],[4,5,6],[7,8,9]] → 12 (เส้นทาง 1→4→7)

แนวคิด: Bottom-up DP แก้ไขในเมทริกซ์เดิม

จากแถวล่างสุดขึ้นบน: dp[i][j] = matrix[i][j] + min(dp[i+1][j-1], dp[i+1][j], dp[i+1][j+1])

ขั้นตอน

  1. n = matrix.size()
  2. ลูป i = n-2 ถึง 0 (ขึ้นจากแถวสุดท้าย-1):
    • ลูป j = 0 ถึง n-1:
      • x1 = (j>0) ? matrix[i+1][j-1] : INF
      • x2 = matrix[i+1][j]
      • x3 = (j+1
      • matrix[i][j] += min(x1, x2, x3)
  3. คืน min ของแถวแรก

ตัวอย่างโค้ด C++

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

class Solution {
public:
    int minFallingPathSum(vector<vector<int>>& a) {
        int n = a.size();
        for (int i = n-2; i >= 0; i--) {
            for (int j = 0; j < n; j++) {
                int x1 = (j > 0) ? a[i+1][j-1] : INT_MAX;
                int x2 = a[i+1][j];
                int x3 = (j+1 < n) ? a[i+1][j+1] : INT_MAX;
                a[i][j] += min({x1, x2, x3});
            }
        }
        int ans = INT_MAX;
        for (int i = 0; i < n; i++) ans = min(ans, a[0][i]);
        return ans;
    }
};

int main() {
    Solution ob;
    vector<vector<int>> v = {{1,2,3},{4,5,6},{7,8,9}};
    cout << ob.minFallingPathSum(v); // 12
    return 0;
}

อินพุต / เอาต์พุต

Input: [[1,2,3],[4,5,6],[7,8,9]]

Output: 12

ความซับซ้อน

  • Time: O(n²)
  • Space: O(1) extra (แก้ใน matrix เดิม)