मान लीजिए हमारे पास धनात्मक पूर्णांकों के साथ एक 2D मैट्रिक्स है। हमें मैट्रिक्स के अंत (सबसे दाएं नीचे का सेल) तक जाने के लिए आवश्यक न्यूनतम चरण खोजने हैं, यदि हम सेल (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 + min(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
