Рубрики

Считает путь в массиве

Дан массив A, состоящий из натурального числа размером N. Если элемент в массиве с индексом i равен K, то вы можете перейти между диапазонами индекса (i + 1) и (i + K) .
Задача состоит в том, чтобы найти количество возможных способов достижения конца с помощью модуля 10 9 + 7 .

Начальная позиция считается индексом 0 .

Примеры:

Input: A = {5, 3, 1, 4, 3}
Output: 6

Input: A = {2, 3, 1, 1, 2}
Output: 4

Наивный подход: мы можем сформировать рекурсивную структуру для решения проблемы.

Пусть F [i] обозначает количество путей, начинающихся с индекса i , для каждого индекса i, если элемент A [i] равен K, тогда общее число способов, которым может быть выполнен переход:

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

Используя эту рекурсивную формулу, мы можем решить проблему:

C ++

// C ++ реализация
// вышеуказанный подход
#include <bits/stdc++.h>

using namespace std;

  

const int mod = 1e9 + 7;

  
// Находим количество способов
// до конца

int ways(int i, int arr[], int n)

{

    // Базовый вариант

    if (i == n - 1)

        return 1;

  

    int sum = 0;

  

    // Рекурсивная структура

    for (int j = 1;

         j + i < n && j <= arr[i];

         j++) {

        sum += (ways(i + j,

                     arr, n))

               % mod;

        sum %= mod;

    }

  

    return sum % mod;

}

  
// Код драйвера

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 реализация
// вышеуказанный подход

import java.io.*;

  

class GFG

{

static int mod = 1000000000;

  
// Находим количество способов
// до конца

static int ways(int i, 

                int arr[], int n)

{

    // Базовый вариант

    if (i == n - 1)

        return 1;

  

    int sum = 0;

  

    // Рекурсивная структура

    for (int j = 1; j + i < n && 

                    j <= arr[i]; j++)

    {

        sum += (ways(i + j,

                     arr, n)) % mod;

        sum %= mod;

    }

    return sum % mod;

}

  
// Код драйвера

public static void main (String[] args)

{

    int arr[] = { 5, 3, 1, 4, 3 };

      

    int n = arr.length;

  

    System.out.println (ways(0, arr, n));

}
}

  
// Этот код предоставлен ajit

python3

# Python3 реализация
# вышеуказанный подход

  

mod = 1e9 + 7;

  
# Найти количество способов
# до конца

def ways(i, arr, n):

      

    # Базовый вариант

    if (i == n - 1):

        return 1;

  

    sum = 0;

  

    # Рекурсивная структура

    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);

  
# Код драйвера

if __name__ == '__main__':

    arr = [5, 3, 1, 4, 3];

  

    n = len(arr);

  

    print(ways(0, arr, n));

  
# Этот код предоставлен PrinciRaj1992

C #

// C # реализация
// вышеуказанный подход

using System;

      

class GFG

{

static int mod = 1000000000;

  
// Находим количество способов
// до конца

static int ways(int i, 

                int []arr, int n)

{

    // Базовый вариант

    if (i == n - 1)

        return 1;

  

    int sum = 0;

  

    // Рекурсивная структура

    for (int j = 1; j + i < n && 

                    j <= arr[i]; j++)

    {

        sum += (ways(i + j,

                     arr, n)) % mod;

        sum %= mod;

    }

    return sum % mod;

}

  
// Код драйвера

public static void Main (String[] args)

{

    int []arr = { 5, 3, 1, 4, 3 };

      

    int n = arr.Length;

  

    Console.WriteLine(ways(0, arr, n));

}
}

  
// Этот код предоставлен 29AjayKumar

Выход:

6

Эффективный подход: в предыдущем подходе есть некоторые расчеты, которые выполняются более одного раза. Лучше хранить эти значения в массиве dp, а dp [i] будет хранить количество путей, начиная с индекса i и заканчивая концом массива.

Следовательно, dp [0] будет решением проблемы.

Ниже приведена реализация подхода:

C ++

// реализация C ++
#include <bits/stdc++.h>

using namespace std;

  

const int mod = 1e9 + 7;

  
// найти количество способов достичь конца

int ways(int arr[], int n)

{

    // дп для хранения значения

    int dp[n + 1];

  

    // базовый вариант

    dp[n - 1] = 1;

  

    // снизу вверх структура дп

    for (int i = n - 2; i >= 0; i--) {

        dp[i] = 0;

  

        // F [i] зависит от

        // F [i + 1] до F [i + k]

        for (int j = 1; ((j + i) < n

                         && j <= arr[i]);

             j++) {

            dp[i] += dp[i + j];

            dp[i] %= mod;

        }

    }

  

    // Возвращаем значение dp [0]

    return dp[0] % mod;

}

  
// Код драйвера

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 реализация вышеупомянутого подхода

class GFG 

{

    static final int mod = (int)(1e9 + 7); 

      

    // найти количество способов достичь конца

    static int ways(int arr[], int n) 

    

        // дп для хранения значения

        int dp[] = new int[n + 1]; 

      

        // базовый вариант

        dp[n - 1] = 1

      

        // снизу вверх структура дп

        for (int i = n - 2; i >= 0; i--) 

        

            dp[i] = 0

      

            // F [i] зависит от

            // F [i + 1] до F [i + k]

            for (int j = 1; ((j + i) < n && 

                              j <= arr[i]); j++)

            

                dp[i] += dp[i + j]; 

                dp[i] %= mod; 

            

        

      

        // Возвращаем значение dp [0]

        return dp[0] % mod; 

    

      

    // Код драйвера

    public static void main (String[] args)

    

        int arr[] = { 5, 3, 1, 4, 3 }; 

      

        int n = arr.length; 

      

        System.out.println(ways(arr, n) % mod); 

    

}

  
// Этот код предоставлен AnkitRai01

C #

// C # реализация вышеуказанного подхода

using System;

      

class GFG 

{

    static readonly int mod = (int)(1e9 + 7); 

      

    // найти количество способов достичь конца

    static int ways(int []arr, int n) 

    

        // дп для хранения значения

        int []dp = new int[n + 1]; 

      

        // базовый вариант

        dp[n - 1] = 1; 

      

        // снизу вверх структура дп

        for (int i = n - 2; i >= 0; i--) 

        

            dp[i] = 0; 

      

            // F [i] зависит от

            // F [i + 1] до F [i + k]

            for (int j = 1; ((j + i) < n && 

                              j <= arr[i]); j++)

            

                dp[i] += dp[i + j]; 

                dp[i] %= mod; 

            

        

      

        // Возвращаем значение dp [0]

        return dp[0] % mod; 

    

      

    // Код драйвера

    public static void Main (String[] args)

    

        int []arr = { 5, 3, 1, 4, 3 }; 

      

        int n = arr.Length; 

      

        Console.WriteLine(ways(arr, n) % mod); 

    

}

  
// Этот код предоставлен Rajput-Ji

Выход:

6

Сложность времени: O (K)

Рекомендуемые посты:

Считает путь в массиве

0.00 (0%) 0 votes