Encuentre los pasos mínimos necesarios para llegar al final de una array | Serie 1

Dada una array 2d que consta de números enteros positivos, la tarea es encontrar el número mínimo de pasos necesarios para llegar al final (la celda inferior izquierda) de la array. Si estamos en la celda (i, j) podemos ir a las celdas (i, j+arr[i][j]) o (i+arr[i][j], j). No podemos salirnos de los límites. Si no existe una ruta, imprima -1.

Ejemplos: 

Input : 
mat[][] = {{2, 1, 2},
           {1, 1, 1},
           {1, 1, 1}}
Output : 2
Explanation : The path will be {0, 0} -> {0, 2} -> {2, 2}
Thus, we are reaching end in two steps.

Input :
mat[][] = {{1, 1, 2},
           {1, 1, 1},
           {2, 1, 1}}
Output : 3

Una solución simple es explorar todas las soluciones posibles. Esto tomará un tiempo exponencial.
Mejor enfoque: podemos usar programación dinámica para resolver este problema en tiempo polinomial.
Decidamos los estados de ‘dp’. Construiremos nuestra solución en 2d DP. 
Digamos que estamos en la celda {i, j}. Intentaremos encontrar el número mínimo de pasos necesarios para llegar a la celda (n-1, n-1) desde esta celda. 
Solo tenemos dos caminos posibles, es decir, a las celdas {i, j+arr[i][j]} o {i+arr[i][j], j}.
Una relación de recurrencia simple será: 

dp[i][j] = 1 + min(dp[i+arr[i][j]][j], dp[i][j+arr[i][j]])

A continuación se muestra la implementación de la idea anterior: 

// C++ program to implement above approach
 
#include <bits/stdc++.h>
#define n 3
using namespace std;
 
// 2d array to store
// states of dp
int dp[n][n];
 
// array to determine whether
// a state has been solved before
int v[n][n];
 
// Function to find the minimum number of
// steps to reach the end of matrix
int minSteps(int i, int j, int arr[][n])
{
    // base cases
    if (i == n - 1 and j == n - 1)
        return 0;
 
    if (i > n - 1 || j > n - 1)
        return 9999999;
 
    // if a state has been solved before
    // it won't be evaluated again.
    if (v[i][j])
        return dp[i][j];
 
    v[i][j] = 1;
 
    // recurrence relation
    dp[i][j] = 1 + min(minSteps(i + arr[i][j], j, arr),
                       minSteps(i, j + arr[i][j], arr));
 
    return dp[i][j];
}
 
// Driver Code
int main()
{
    int arr[n][n] = { { 2, 1, 2 },
                      { 1, 1, 1 },
                      { 1, 1, 1 } };
 
    int ans = minSteps(0, 0, arr);
    if (ans >= 9999999)
        cout << -1;
    else
        cout << ans;
 
    return 0;
}

// Java program to implement above approach
class GFG {
 
    static int n = 3;
 
    // 2d array to store
    // states of dp
    static int dp[][] = new int[n][n];
 
    // array to determine whether
    // a state has been solved before
    static int[][] v = new int[n][n];
 
    // Function to find the minimum number of
    // steps to reach the end of matrix
    static int minSteps(int i, int j, int arr[][])
    {
        // base cases
        if (i == n - 1 && j == n - 1) {
            return 0;
        }
 
        if (i > n - 1 || j > n - 1) {
            return 9999999;
        }
 
        // if a state has been solved before
        // it won't be evaluated again.
        if (v[i][j] == 1) {
            return dp[i][j];
        }
 
        v[i][j] = 1;
 
        // recurrence relation
        dp[i][j] = 1 + Math.min(minSteps(i + arr[i][j], j, arr), minSteps(i, j + arr[i][j], arr));
 
        return dp[i][j];
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int arr[][] = { { 2, 1, 2 },
                        { 1, 1, 1 },
                        { 1, 1, 1 } };
 
        int ans = minSteps(0, 0, arr);
        if (ans >= 9999999) {
            System.out.println(-1);
        }
        else {
            System.out.println(ans);
        }
    }
}
 
// This code contributed by Rajput-Ji

# Python3 program to implement above approach
import numpy as np;
 
n = 3
 
# 2d array to store
# states of dp
dp = np.zeros((n, n));
 
# array to determine whether
# a state has been solved before
v = np.zeros((n, n));
 
# Function to find the minimum number of
# steps to reach the end of matrix
def minSteps(i, j, arr) :
 
    # base cases
    if (i == n - 1 and j == n - 1) :
        return 0;
 
    if (i > n - 1 or j > n - 1) :
        return 9999999;
 
    # if a state has been solved before
    # it won't be evaluated again.
    if (v[i][j]) :
        return dp[i][j];
 
    v[i][j] = 1;
 
    # recurrence relation
    dp[i][j] = 1 + min(minSteps(i + arr[i][j], j, arr),
                    minSteps(i, j + arr[i][j], arr));
 
    return dp[i][j];
 
 
# Driver Code
arr = [ [ 2, 1, 2 ],
            [ 1, 1, 1 ],
            [ 1, 1, 1 ]
            ];
             
ans = minSteps(0, 0, arr);
if (ans >= 9999999) :
    print(-1);
         
else :
    print(ans);
 
# This code is contributed by AnkitRai01

// C# program to implement above approach
using System;
 
class GFG
{
     
    static int n = 3;
 
    // 2d array to store
    // states of dp
    static int [,]dp = new int[n, n];
 
    // array to determine whether
    // a state has been solved before
    static int[,] v = new int[n, n];
 
    // Function to find the minimum number of
    // steps to reach the end of matrix
    static int minSteps(int i, int j, int [,]arr)
    {
        // base cases
        if (i == n - 1 && j == n - 1)
        {
            return 0;
        }
 
        if (i > n - 1 || j > n - 1)
        {
            return 9999999;
        }
 
        // if a state has been solved before
        // it won't be evaluated again.
        if (v[i, j] == 1)
        {
            return dp[i, j];
        }
 
        v[i, j] = 1;
 
        // recurrence relation
        dp[i, j] = 1 + Math.Min(minSteps(i + arr[i,j], j, arr),
                            minSteps(i, j + arr[i,j], arr));
 
        return dp[i, j];
    }
 
    // Driver Code
    static public void Main ()
    {
        int [,]arr = { { 2, 1, 2 },
                        { 1, 1, 1 },
                        { 1, 1, 1 } };
 
        int ans = minSteps(0, 0, arr);
        if (ans >= 9999999)
        {
            Console.WriteLine(-1);
        }
        else
        {
            Console.WriteLine(ans);
        }
    }
}
 
// This code contributed by ajit.

<script>
 
    // Javascript program to implement
    // above approach
     
    let n = 3;
   
    // 2d array to store
    // states of dp
    let dp = new Array(n);
    for(let i = 0; i < n; i++)
    {
        dp[i] = new Array(n);
    }
   
    // array to determine whether
    // a state has been solved before
    let v = new Array(n);
    for(let i = 0; i < n; i++)
    {
        v[i] = new Array(n);
    }
   
    // Function to find the minimum number of
    // steps to reach the end of matrix
    function minSteps(i, j, arr)
    {
        // base cases
        if (i == n - 1 && j == n - 1)
        {
            return 0;
        }
   
        if (i > n - 1 || j > n - 1)
        {
            return 9999999;
        }
   
        // if a state has been solved before
        // it won't be evaluated again.
        if (v[i][j] == 1) {
            return dp[i][j];
        }
   
        v[i][j] = 1;
   
        // recurrence relation
        dp[i][j] = 1 + Math.min(minSteps(i +
        arr[i][j], j, arr), minSteps(i, j + arr[i][j], arr));
   
        return dp[i][j];
    }
     
    let arr = [ [ 2, 1, 2 ],
               [ 1, 1, 1 ],
               [ 1, 1, 1 ] ];
   
    let ans = minSteps(0, 0, arr);
    if (ans >= 9999999) {
      document.write(-1);
    }
    else {
      document.write(ans);
    }
     
</script>

2

Complejidad temporal : O(N ² ).