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

สมมติว่าเรามีอาร์เรย์กำลังสองของจำนวนเต็ม A เราต้องการผลรวมขั้นต่ำของเส้นทางล้มผ่าน A โดยพื้นฐานแล้วเส้นทางล้มนั้นเป็นเส้นทางที่เริ่มต้นที่องค์ประกอบใดๆ ในแถวแรก และเลือกหนึ่งองค์ประกอบจากแต่ละแถว และองค์ประกอบของแถวถัดไปต้องอยู่ในคอลัมน์ที่แตกต่างจากคอลัมน์ของแถวก่อนหน้าอย่างน้อยหนึ่งคอลัมน์ ดังนั้นหากเมทริกซ์เป็นเหมือน −

จากนั้นผลลัพธ์คือ 12 มีเส้นทางล้มที่แตกต่างกันเล็กน้อย ได้แก่ [1,4,7], [1,4,8], [1,5,7], [1,5,8], [1,5,9], [2,4,7], [2,4,8], [2,5,7], [2,5,8], [2,5,9], [2,6,9], [3,5,7], [3 ,5,8], [3,5,9], [3,6,8], [3,6,9] และเส้นทางผลรวมที่น้อยที่สุดคือ [1,4,7] และผลรวมคือ 12

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• n :=ขนาดของอาร์เรย์
• สำหรับ i ในช่วง n – 2 เหลือ 0
  • สำหรับ j ในช่วง 0 ถึง n
    • ถ้า j – 1 <0 แล้ว x1 :=inf มิฉะนั้น x1 :=matrix[i + 1, j - 1]
    • x2 :=เมทริกซ์[i + 1, j]
    • ถ้า j + 1>=n แล้ว x3 :=inf มิฉะนั้น x3 :=matrix[i + 1, j + 1]
    • เมทริกซ์[i, j] :=เมทริกซ์[i, j] + ต่ำสุดของ x1, x2, x3
• ตอบ :=inf
• สำหรับ i ในช่วง 0 ถึง n – 1
  • ans :=นาทีของ ans และ matrix[0, i]
• คืนสินค้า

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

#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-1<0?INT_MAX:a[i+1][j-1];
            int x2 = a[i+1][j];
            int x3 = j+1>=n?INT_MAX:a[i+1][j+1];
            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;
   }
};
main(){
   vector<vector<int>> v = {{1,2,3},{4,5,6},{7,8,9}};
   Solution ob;
   cout <<(ob.minFallingPathSum(v));
}

อินพุต

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

ผลลัพธ์

12