Falling Path Sum II ขั้นต่ำใน C++

สมมติว่าเรามีกริด arr นี่คือตารางสี่เหลี่ยม เส้นทางล้มที่มีการเลื่อนที่ไม่ใช่ศูนย์คือตัวเลือกหนึ่งองค์ประกอบจากแต่ละแถวของ arr โดยที่ไม่มีองค์ประกอบสองรายการที่เลือกในแถวที่อยู่ติดกันปรากฏในคอลัมน์เดียวกัน เราต้องหาผลรวมขั้นต่ำของเส้นทางล้มด้วยการเลื่อนที่ไม่ใช่ศูนย์

ดังนั้น หากอินพุตเป็นเหมือน arr เหมือนกับ [[1,2,3],[4,5,6],[7,8,9]] ผลลัพธ์จะเป็น 13 เนื่องจากมีเส้นทางตกที่แตกต่างกัน เช่น [1,5,9], [1,5,7], [1,6,7], [1,6,8], [2,4,8], [2,4,9] , [2,6,7], [2,6,8], [3,4,8], [3,4,9], [3,5,7], [3,5,9]. ตอนนี้เส้นทางตกที่มีผลรวมน้อยที่สุดคือ [1,5,7] ดังนั้นคำตอบคือ 13

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

• n :=จำนวนแถว, m :=จำนวนคอลัมน์

• สำหรับการเริ่มต้น i :=1 เมื่อฉัน

  • กำหนดอาร์เรย์ leftMin และ rightMin ของขนาด m

  • leftMin[0] :=arr[i - 1, 0]

  • สำหรับการเริ่มต้น j :=1 เมื่อ j

    • leftMin[j] :=ขั้นต่ำของ leftMin[j - 1] และ arr[i - 1, j]

  • rightMin[m - 1] =arr[i - 1, m - 1]

  • สำหรับการเริ่มต้น j :=m - 2 เมื่อ j>=0, อัปเดต (ลด j โดย 1) ให้ทำ -

    • rightMin[j] :=ขั้นต่ำของ arr[i - 1, j] และ rightMin[j + 1]

  • สำหรับการเริ่มต้น j :=0 เมื่อ j

    • leftVal :=(ถ้า (j - 1)>=0 แล้ว leftMin[j - 1] มิฉะนั้น 1000000)

    • rightVal :=(ถ้า (j + 1)

    • arr[i, j] :=arr[i, j] + min(leftVal, rightVal)

• ตอบ :=inf

• สำหรับการเริ่มต้น i :=0 เมื่อ i

  • ans :=ขั้นต่ำของ ans และ arr[n - 1, i]

• กลับมาอีกครั้ง

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

ตัวอย่าง

#include ใช้เนมสเปซ std;int dp[10005][205];class Solution { สาธารณะ:void pre(){ สำหรับ (int i =0; i <=10000; i++){ สำหรับ(int j =0; j <=204; j++){ dp[i][j] =-1; } } } int minFallingPathSum(vector>&arr) { int n =arr.size(); int m =arr[0].size(); สำหรับ (int i =1; i  leftMin(m); เวกเตอร์ rightMin(m); leftMin[0] =arr[i - 1][0]; สำหรับ (int j =1; j =0; j--) { rightMin[j] =min(arr[i - 1][j], rightMin[j + 1]); } สำหรับ (int j =0; j =0 ? leftMin[j - 1] :1000000; int rightVal =(j + 1) <ม ? rightMin[j + 1] :1000000; arr[i][j] +=min(leftVal, rightVal); } } int ans =INT_MAX; สำหรับ (int i =0; i > v ={{1,2,3},{4,5,6},{7,8,9}}; cout <<(ob.minFallingPathSum(v));}

อินพุต

ผลลัพธ์

13