C++でマトリックスの最後に到達するために必要な最小ステップを見つける

正の整数を持つ2D行列があるとします。マトリックスの最後（右下のセル）に移動するために必要な最小ステップを見つける必要があります。セル（i、j）にいる場合は、セル（i、j + mat [i、j）に移動できます。 ]）または（i + mat [i、j]、j）、境界を越えることはできません。したがって、行列が-

出力は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