Dada una array de enteros arr[] de longitud N que consta de enteros positivos, la tarea es minimizar el número de pasos necesarios para alcanzar el índice ‘N-1’. En un paso dado, si estamos en el índice ‘i’, podemos ir al índice ‘i-arr[i]’ o ‘i+arr[i]’ dado que no hemos visitado esos índices antes. Además, no podemos salirnos de los límites de la array. Imprime -1 si no hay forma posible.
Ejemplos:
Input : arr[] = {1, 1, 1}
Output : 2
The path will be 0 -> 1 -> 2.
Step 1 - 0 to 1
Step 2 - 1 to 2
Input : {2, 1}
Output : -1
Este problema se puede resolver utilizando el enfoque de programación dinámica.
Analicemos un enfoque que podría parecer correcto al principio . Supongamos que estamos en i- ésimo índice. ¿Podemos decir directamente que dp[i] = 1 + min( dp[i-arr[i]], dp[i+arr[i]] ) ?
No podemos. El camino que tomamos para llegar al índice ‘i’ también importa, ya que los índices que usamos antes ya no estarán disponibles para visitar.
Por lo tanto, el único enfoque que nos queda es probar todas las combinaciones posibles que pueden ser realmente grandes. En este artículo, utilizaremos un enfoque de enmascaramiento de bits para reducir la complejidad a exponencial. Nuestra máscara será un valor entero con las siguientes características.
1) If, a index 'i' is visited, ith bit will be set 1 in the mask. 2) Else that bit will be set 0.
La relación de recurrencia requerida será.
dp[i][mask] = 1 + min(dp[i+arr[i]][mask|(1<<i)],
dp[i-arr[i]][mask|(1<<i)])
A continuación se muestra la implementación del enfoque anterior:
CPP
// C++ implementation of the above approach
#include <bits/stdc++.h>
#define maxLen 10
#define maskLen 130
using namespace std;
// variable to store states of dp
int dp[maxLen][maskLen];
// variable to check if a given state
// has been solved
bool v[maxLen][maskLen];
// Function to find the minimum number of steps
// required to reach the end of the array
int minSteps(int arr[], int i, int mask, int n)
{
// base case
if (i == n - 1)
return 0;
if (i > n - 1 || i < 0)
return 9999999;
if ((mask >> i) & 1)
return 9999999;
// to check if a state has
// been solved
if (v[i][mask])
return dp[i][mask];
v[i][mask] = 1;
// required recurrence relation
dp[i][mask] = 1 + min(minSteps(arr, i - arr[i], (mask | (1 << i)), n),
minSteps(arr, i + arr[i], (mask | (1 << i)), n));
// returning the value
return dp[i][mask];
}
// Driver code
int main()
{
int arr[] = { 1, 2, 2, 2, 1, 1 };
int n = sizeof(arr) / sizeof(int);
int ans = minSteps(arr, 0, 0, n);
if (ans >= 9999999)
cout << -1;
else
cout << ans;
}
Java
// Java implementation of the above approach
class GFG
{
static int maxLen = 10;
static int maskLen = 130;
// variable to store states of dp
static int[][] dp = new int[maxLen][maskLen];
// variable to check if a given state
// has been solved
static boolean[][] v = new boolean[maxLen][maskLen];
// Function to find the minimum number of steps
// required to reach the end of the array
static int minSteps(int arr[], int i, int mask, int n)
{
// base case
if (i == n - 1)
{
return 0;
}
if (i > n - 1 || i < 0)
{
return 9999999;
}
if ((mask >> i) % 2 == 1)
{
return 9999999;
}
// to check if a state has
// been solved
if (v[i][mask])
{
return dp[i][mask];
}
v[i][mask] = true;
// required recurrence relation
dp[i][mask] = 1 + Math.min(minSteps(arr, i - arr[i], (mask | (1 << i)), n),
minSteps(arr, i + arr[i], (mask | (1 << i)), n));
// returning the value
return dp[i][mask];
}
// Driver code
public static void main(String[] args)
{
int arr[] = {1, 2, 2, 2, 1, 1};
int n = arr.length;
int ans = minSteps(arr, 0, 0, n);
if (ans >= 9999999)
{
System.out.println(-1);
}
else
{
System.out.println(ans);
}
}
}
/* This code contributed by PrinciRaj1992 */
Python
# Python3 implementation of the above approach maxLen = 10 maskLen = 130 # variable to store states of dp dp = [[ 0 for i in range(maskLen)] for i in range(maxLen)] # variable to check if a given state # has been solved v = [[False for i in range(maskLen)] for i in range(maxLen)] # Function to find the minimum number of steps # required to reach the end of the array def minSteps(arr, i, mask, n): # base case if (i == n - 1): return 0 if (i > n - 1 or i < 0): return 9999999 if ((mask >> i) & 1): return 9999999 # to check if a state has # been solved if (v[i][mask] == True): return dp[i][mask] v[i][mask] = True # required recurrence relation dp[i][mask] = 1 + min(minSteps(arr, i - arr[i], (mask | (1 << i)), n), minSteps(arr, i + arr[i], (mask | (1 << i)), n)) # returning the value return dp[i][mask] # Driver code arr=[1, 2, 2, 2, 1, 1] n = len(arr) ans = minSteps(arr, 0, 0, n) if (ans >= 9999999): print(-1) else: print(ans) # This code is contributed by mohit kumar 29
C#
// C# implementation of the above approach
using System;
class GFG
{
static int maxLen = 10;
static int maskLen = 130;
// variable to store states of dp
static int[,] dp = new int[maxLen, maskLen];
// variable to check if a given state
// has been solved
static bool[,] v = new bool[maxLen, maskLen];
// Function to find the minimum number of steps
// required to reach the end of the array
static int minSteps(int []arr, int i, int mask, int n)
{
// base case
if (i == n - 1)
{
return 0;
}
if (i > n - 1 || i < 0)
{
return 9999999;
}
if ((mask >> i) % 2 == 1)
{
return 9999999;
}
// to check if a state has
// been solved
if (v[i, mask])
{
return dp[i, mask];
}
v[i, mask] = true;
// required recurrence relation
dp[i,mask] = 1 + Math.Min(minSteps(arr, i - arr[i], (mask | (1 << i)), n),
minSteps(arr, i + arr[i], (mask | (1 << i)), n));
// returning the value
return dp[i,mask];
}
// Driver code
static public void Main ()
{
int []arr = {1, 2, 2, 2, 1, 1};
int n = arr.Length;
int ans = minSteps(arr, 0, 0, n);
if (ans >= 9999999)
{
Console.WriteLine(-1);
}
else
{
Console.WriteLine(ans);
}
}
}
/* This code contributed by ajit. */
Javascript
<script>
// Javascript implementation of
// the above approach
let maxLen = 10;
let maskLen = 130;
// variable to store states of dp
let dp = new Array(maxLen);
for(let i = 0; i < maxLen; i++)
{
dp[i] = new Array(maskLen);
}
// variable to check if a given state
// has been solved
let v = new Array(maxLen);
for(let i = 0; i < maxLen; i++)
{
v[i] = new Array(maskLen);
}
// Function to find the minimum number of steps
// required to reach the end of the array
function minSteps(arr, i, mask, n)
{
// base case
if (i == n - 1)
{
return 0;
}
if (i > n - 1 || i < 0)
{
return 9999999;
}
if ((mask >> i) % 2 == 1)
{
return 9999999;
}
// to check if a state has
// been solved
if (v[i][mask])
{
return dp[i][mask];
}
v[i][mask] = true;
// required recurrence relation
dp[i][mask] = 1 + Math.min(minSteps(arr, i - arr[i],
(mask | (1 << i)), n), minSteps(arr, i + arr[i],
(mask | (1 << i)), n));
// returning the value
return dp[i][mask];
}
let arr = [1, 2, 2, 2, 1, 1];
let n = arr.length;
let ans = minSteps(arr, 0, 0, n);
if (ans >= 9999999)
{
document.write(-1);
}
else
{
document.write(ans);
}
</script>
3
Complejidad del tiempo : O(N*(2 N ))
Espacio auxiliar: O (maxLen + maskLen)
Publicación traducida automáticamente
Artículo escrito por DivyanshuShekhar1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA