ধরুন আমাদের ধনাত্মক পূর্ণসংখ্যা সহ একটি 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+মিনিট (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
