Cuenta la ruta en una array

Dada una array A que consta de enteros positivos, de tamaño N . Si el elemento en la array en el índice i es K , entonces puede saltar entre los rangos de índice (i + 1) a (i + K) . 
La tarea es encontrar el número de formas posibles de llegar al final con el módulo 10 ⁹ + 7 .
La posición inicial se considera como índice 0 .
Ejemplos: 
 

Entrada: A = {5, 3, 1, 4, 3} 
Salida: 6
Entrada: A = {2, 3, 1, 1, 2} 
Salida: 4 
 

Enfoque ingenuo: podemos formar una estructura recursiva para resolver el problema.
Sea F[i] el número de rutas que comienzan en el índice i , en cada índice i si el elemento A[i] es K , entonces el número total de formas en que se puede realizar el salto es: 
 

F(i) = F(i+1) + F(i+2) +...+ F(i+k), where i + k <= n, 
where F(n) = 1

Usando esta fórmula recursiva podemos resolver el problema:
 

// C++ implementation of
// the above approach
#include <bits/stdc++.h>
using namespace std;
 
const int mod = 1e9 + 7;
 
// Find the number of ways
// to reach the end
int ways(int i, int arr[], int n)
{
    // Base case
    if (i == n - 1)
        return 1;
 
    int sum = 0;
 
    // Recursive structure
    for (int j = 1;
         j + i < n && j <= arr[i];
         j++) {
        sum += (ways(i + j,
                     arr, n))
               % mod;
        sum %= mod;
    }
 
    return sum % mod;
}
 
// Driver code
int main()
{
    int arr[] = { 5, 3, 1, 4, 3 };
 
    int n = sizeof(arr) / sizeof(arr[0]);
 
    cout << ways(0, arr, n) << endl;
 
    return 0;
}

// Java implementation of
// the above approach
import java.io.*;
 
class GFG
{
static int mod = 1000000000;
 
// Find the number of ways
// to reach the end
static int ways(int i,
                int arr[], int n)
{
    // Base case
    if (i == n - 1)
        return 1;
 
    int sum = 0;
 
    // Recursive structure
    for (int j = 1; j + i < n &&
                    j <= arr[i]; j++)
    {
        sum += (ways(i + j,
                     arr, n)) % mod;
        sum %= mod;
    }
    return sum % mod;
}
 
// Driver code
public static void main (String[] args)
{
    int arr[] = { 5, 3, 1, 4, 3 };
     
    int n = arr.length;
 
    System.out.println (ways(0, arr, n));
}
}
 
// This code is contributed by ajit

# Python3 implementation of
# the above approach
 
mod = 1e9 + 7;
 
# Find the number of ways
# to reach the end
def ways(i, arr, n):
     
    # Base case
    if (i == n - 1):
        return 1;
 
    sum = 0;
 
    # Recursive structure
    for j in range(1, arr[i] + 1):
        if(i + j < n):
            sum += (ways(i + j, arr, n)) % mod;
            sum %= mod;
 
    return int(sum % mod);
 
# Driver code
if __name__ == '__main__':
    arr = [5, 3, 1, 4, 3];
 
    n = len(arr);
 
    print(ways(0, arr, n));
 
# This code is contributed by PrinciRaj1992

// C# implementation of
// the above approach
using System;
     
class GFG
{
static int mod = 1000000000;
 
// Find the number of ways
// to reach the end
static int ways(int i,
                int []arr, int n)
{
    // Base case
    if (i == n - 1)
        return 1;
 
    int sum = 0;
 
    // Recursive structure
    for (int j = 1; j + i < n &&
                    j <= arr[i]; j++)
    {
        sum += (ways(i + j,
                     arr, n)) % mod;
        sum %= mod;
    }
    return sum % mod;
}
 
// Driver code
public static void Main (String[] args)
{
    int []arr = { 5, 3, 1, 4, 3 };
     
    int n = arr.Length;
 
    Console.WriteLine(ways(0, arr, n));
}
}
 
// This code is contributed by 29AjayKumar

<script>
    // Javascript implementation of the above approach
     
    let mod = 1000000000;
   
    // Find the number of ways
    // to reach the end
    function ways(i, arr, n)
    {
        // Base case
        if (i == n - 1)
            return 1;
 
        let sum = 0;
 
        // Recursive structure
        for (let j = 1; j + i < n && j <= arr[i]; j++)
        {
            sum += (ways(i + j, arr, n)) % mod;
            sum %= mod;
        }
        return sum % mod;
    }
     
    let arr = [ 5, 3, 1, 4, 3 ];
       
    let n = arr.length;
   
    document.write(ways(0, arr, n));
     
</script>

6

Enfoque eficiente: en el enfoque anterior, hay algunos cálculos que se realizan más de una vez. Será mejor almacenar estos valores en una array dp y dp[i] almacenará la cantidad de rutas que comienzan en el índice i y terminan al final de la array.
Por lo tanto, dp[0] será la solución al problema.
A continuación se muestra la implementación del enfoque:
 

// C++ implementation
#include <bits/stdc++.h>
using namespace std;
 
const int mod = 1e9 + 7;
 
// find the number of ways to reach the end
int ways(int arr[], int n)
{
    // dp to store value
    int dp[n + 1];
 
    // base case
    dp[n - 1] = 1;
 
    // Bottom up dp structure
    for (int i = n - 2; i >= 0; i--) {
        dp[i] = 0;
 
        // F[i] is dependent of
        // F[i+1] to F[i+k]
        for (int j = 1; ((j + i) < n
                         && j <= arr[i]);
             j++) {
            dp[i] += dp[i + j];
            dp[i] %= mod;
        }
    }
 
    // Return value of dp[0]
    return dp[0] % mod;
}
 
// Driver code
int main()
{
    int arr[] = { 5, 3, 1, 4, 3 };
 
    int n = sizeof(arr) / sizeof(arr[0]);
 
    cout << ways(arr, n) % mod << endl;
    return 0;
}

// Java implementation of above approach
class GFG
{
    static final int mod = (int)(1e9 + 7);
     
    // find the number of ways to reach the end
    static int ways(int arr[], int n)
    {
        // dp to store value
        int dp[] = new int[n + 1];
     
        // base case
        dp[n - 1] = 1;
     
        // Bottom up dp structure
        for (int i = n - 2; i >= 0; i--)
        {
            dp[i] = 0;
     
            // F[i] is dependent of
            // F[i+1] to F[i+k]
            for (int j = 1; ((j + i) < n &&
                              j <= arr[i]); j++)
            {
                dp[i] += dp[i + j];
                dp[i] %= mod;
            }
        }
     
        // Return value of dp[0]
        return dp[0] % mod;
    }
     
    // Driver code
    public static void main (String[] args)
    {
        int arr[] = { 5, 3, 1, 4, 3 };
     
        int n = arr.length;
     
        System.out.println(ways(arr, n) % mod);
    }
}
 
// This code is contributed by AnkitRai01

# Python3 implementation of above approach
mod = 10**9 + 7
 
# find the number of ways to reach the end
def ways(arr, n):
     
    # dp to store value
    dp = [0] * (n + 1)
     
    # base case
    dp[n - 1] = 1
     
    # Bottom up dp structure
    for i in range(n - 2, -1, -1):
        dp[i] = 0
         
        # F[i] is dependent of
        # F[i + 1] to F[i + k]
        j = 1
        while((j + i) < n and j <= arr[i]):
            dp[i] += dp[i + j]
            dp[i] %= mod
            j += 1
     
    # Return value of dp[0]
    return dp[0] % mod
 
# Driver code
arr = [5, 3, 1, 4, 3 ]
n = len(arr)
print(ways(arr, n) % mod)
 
# This code is contributed by SHUBHAMSINGH10

// C# implementation of above approach
using System;
     
class GFG
{
    static readonly int mod = (int)(1e9 + 7);
     
    // find the number of ways to reach the end
    static int ways(int []arr, int n)
    {
        // dp to store value
        int []dp = new int[n + 1];
     
        // base case
        dp[n - 1] = 1;
     
        // Bottom up dp structure
        for (int i = n - 2; i >= 0; i--)
        {
            dp[i] = 0;
     
            // F[i] is dependent of
            // F[i+1] to F[i+k]
            for (int j = 1; ((j + i) < n &&
                              j <= arr[i]); j++)
            {
                dp[i] += dp[i + j];
                dp[i] %= mod;
            }
        }
     
        // Return value of dp[0]
        return dp[0] % mod;
    }
     
    // Driver code
    public static void Main (String[] args)
    {
        int []arr = { 5, 3, 1, 4, 3 };
     
        int n = arr.Length;
     
        Console.WriteLine(ways(arr, n) % mod);
    }
}
 
// This code is contributed by Rajput-Ji

<script>
 
    // Javascript implementation
    // of above approach
     
    let mod = (1e9 + 7);
       
    // find the number of ways
    // to reach the end
    function ways(arr, n)
    {
        // dp to store value
        let dp = new Array(n + 1);
        dp.fill(0);
       
        // base case
        dp[n - 1] = 1;
       
        // Bottom up dp structure
        for (let i = n - 2; i >= 0; i--)
        {
            dp[i] = 0;
       
            // F[i] is dependent of
            // F[i+1] to F[i+k]
            for (let j = 1; ((j + i)
            < n && j <= arr[i]); j++)
            {
                dp[i] += dp[i + j];
                dp[i] %= mod;
            }
        }
       
        // Return value of dp[0]
        return dp[0] % mod;
    }
     
    let arr = [ 5, 3, 1, 4, 3 ];
       
    let n = arr.length;
 
    document.write(ways(arr, n) % mod);
     
</script>

6

Complejidad de tiempo: O(K)

Espacio Auxiliar: O(n)