Giả sử chúng ta có một ma trận 2D với các số nguyên dương. Chúng ta phải tìm các bước tối thiểu cần thiết để di chuyển từ đến cuối ma trận (ô dưới cùng bên phải), Nếu chúng ta đang ở ô (i, j), chúng ta có thể đi đến ô (i, j + mat [i, j ]) hoặc (i + mat [i, j], j), Chúng ta không thể vượt qua giới hạn. Vì vậy, nếu ma trận giống như -
| 2 | 1 | 2 |
| 1 | 1 | 1 |
| 1 | 1 | 1 |
Đầu ra sẽ là 2. Đường dẫn sẽ là (0, 0) → (0, 2) → (2, 2)
Ở đây chúng tôi sẽ sử dụng cách tiếp cận Lập trình động để giải quyết vấn đề này. Giả sử chúng ta đang ở ô (i, j), chúng ta muốn đến (n-1, n-1) ô. Chúng ta có thể sử dụng quan hệ lặp lại như bên dưới -
DP [i, j] =1 + phút (DP [i + arr [i, j], j], DP [i, j + arr [i, j]])
Ví dụ
#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;
} Đầu ra
Number of steps: 2