สมมติว่าเรามีเมทริกซ์ 2 มิติที่มีจำนวนเต็มบวก เราต้องหาขั้นตอนขั้นต่ำที่จำเป็นในการย้ายจากจุดสิ้นสุดของเมทริกซ์ (เซลล์ล่างสุดทางขวาสุด) ถ้าเราอยู่ที่เซลล์ (i, j) เราสามารถไปที่เซลล์ได้ (i, j+mat[i, j ]) หรือ (i+mat[i, j], j) เราข้ามขอบเขตไม่ได้ ดังนั้นหากเมทริกซ์เป็นเหมือน −
| 2 | 1 | 2 |
| 1 | 1 | 1 |
| 1 | 1 | 1 |
ผลลัพธ์จะเป็น 2 เส้นทางจะเป็น (0, 0) →(0, 2) → (2, 2)
ที่นี่เราจะใช้แนวทางการเขียนโปรแกรมแบบไดนามิกเพื่อแก้ปัญหานี้ สมมติว่าเราอยู่ที่เซลล์ (i, j) เราต้องการเข้าถึงเซลล์ (n-1, n-1) เราสามารถใช้ความสัมพันธ์การเกิดซ้ำได้ดังนี้ −
DP[i, j]=1+นาที (DP [i+arr [i , j] , j], DP[i , j+arr [ i , j]])
ตัวอย่าง
#include<iostream>
#define N 3
using namespace std;
int table[N][N];
bool temp_val[N][N];
int countSteps(int i, int j, int arr[][N]) {
if (i == N - 1 and j == N - 1)
return 0;
if (i > N - 1 || j > N - 1)
return INT_MAX;
if (temp_val[i][j])
return table[i][j];
temp_val[i][j] = true;
table[i][j] = 1 + min(countSteps(i + arr[i][j], j, arr), countSteps(i, j + arr[i][j], arr));
return table[i][j];
}
int main() {
int arr[N][N] = { { 2, 1, 2 }, { 1, 1, 1 }, { 1, 1, 1 } };
int ans = countSteps(0, 0, arr);
if (ans >= INT_MAX)
cout << -1;
else
cout <<"Number of steps: "<< ans;
} ผลลัพธ์
Number of steps: 2
