Дан массив 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 ++
#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;
}
|
Джава
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));
}
}
|
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));
|
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));
}
}
|
Выход:
6
Эффективный подход: в предыдущем подходе есть некоторые расчеты, которые выполняются более одного раза. Лучше хранить эти значения в массиве dp, а dp [i] будет хранить количество путей, начиная с индекса i и заканчивая концом массива.
Следовательно, dp [0] будет решением проблемы.
Ниже приведена реализация подхода:
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;
for (int j = 1; ((j + i) < n
&& j <= arr[i]);
j++) {
dp[i] += dp[i + j];
dp[i] %= mod;
}
}
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;
}
|
Джава
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;
for (int j = 1; ((j + i) < n &&
j <= arr[i]); j++)
{
dp[i] += dp[i + j];
dp[i] %= mod;
}
}
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);
}
}
|
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;
for (int j = 1; ((j + i) < n &&
j <= arr[i]); j++)
{
dp[i] += dp[i + j];
dp[i] %= mod;
}
}
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);
}
}
|
Выход:
6
Сложность времени: O (K)
Рекомендуемые посты:
Считает путь в массиве
0.00 (0%) 0 votes