मान लीजिए कि हमारे पास सकारात्मक पूर्णांक के साथ एक 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