Как я могу еще больше уменьшить временную сложность этого решения?

Я пытался выполнить нижеприведенную задачу. Я пробовал несколько способов решить проблему, но ни один из них не выдержал установленного срока. Пожалуйста, посоветуйте, если у вас есть идея улучшить это.

Проблема:
Вы посещаете здание из N этажей. На каждом этаже есть только одна лестница указанной длины. Если длина лестницы составляет x единиц, вы можете подняться на y этажей выше текущей.

Вы можете оставить лестницу между ними, чтобы ее сменить, но начинать можно только с начального этажа лестницы.

Вам задают Q вопросов. В каждом вопросе вам будет указан номер этажа. Для каждого вопроса вы должны указать наименьшее количество лестниц, необходимых для достижения данного этажа. Изначально вы находитесь на первом этаже.

Формат ввода:
Первая строка содержит целое число T, обозначающее количество тестовых случаев. Для каждого тестового примера: первая строка содержит целое число N, указывающее количество этажей в здании. Следующая строка содержит N разделенных пробелом положительных целых чисел, которые обозначают длину лестницы на каждом этаже (первое целое число соответствует длине лестницы на первом этаже, второе целое число соответствует длине лестницы на первом этаже и т. Д.). Следующая строка содержит целое число Q, обозначающее количество вопросов. В каждой из следующих Q строк записано целое число, обозначающее номер этажа, для которого нужно вычислить ответ.

Выходной формат:
Для каждого вопроса выведите наименьшее количество лестниц, необходимых для достижения данного этажа. Ответ на каждый вопрос должен быть написан с новой строки.

Пример ввода:

1
10
2 2 1 1 2 2 3 1 1 1
10
5
4
3
2
1
10
9
8
7
6

Пример вывода:

4
3
2
1
1
6
5
5
5
4

Ссылка на проблему

Решение:

class Program
{
    static void Main(string[] args)
    {
        int T = Convert.ToInt32(Console.ReadLine());
        StringBuilder sb = new StringBuilder("");
        for (int i = 0; i < T; i++)
        {
            int N = Convert.ToInt32(Console.ReadLine());
            sb.EnsureCapacity(sb.Length + (5 * N));
            int[] numOfStairs = new int[N + 1];
            numOfStairs[0] = 0;
            string[] stairs = Console.ReadLine().Split();
            int[] reaches = new int[N];
            for (int j = 0; j < stairs.Length; j++)
            {
                int length = Convert.ToInt32(stairs[j]);
                reaches[j] = j + length;
            }
            int Q = Convert.ToInt32(Console.ReadLine());

            for (int j = 0; j < Q; j++)
            {
                int target = Convert.ToInt32(Console.ReadLine());
                sb.AppendLine(GetShortestPath(target, reaches.Take(target).ToArray(), numOfStairs).ToString());
            }
        }
        Console.WriteLine(sb.ToString());
    }
    static int GetShortestPath(int target, int[] reaches, int[] numOfStairs)
    {
        if (numOfStairs[target] == 0 && target != 0)
        {
            List<int> connectedFloors = GetPreviousFloorList(target, reaches);
            int[] shortestPaths = new int[connectedFloors.Count];
            for (int i = 0; i < connectedFloors.Count; i++)
            {
                int shortestPath = GetShortestPath(connectedFloors[i], reaches.Take(connectedFloors[i]).ToArray(), numOfStairs);
                shortestPaths[i] = shortestPath;
            }
            int result = shortestPaths.Min() + 1;
            numOfStairs[target] = result;
            return result;
        }
        else
        {
            return numOfStairs[target];
        }
    }
    static List<int> GetPreviousFloorList(int target, int[] reaches)
    {
        List<int> floors = new List<int>(target / 2);
        for (int i = 0; i < target; i++)
        {
            if (reaches[i] >= target)
                floors.Add(i);
        }
        return floors;
    }
}

Я, наконец, смог уменьшить его настолько, чтобы вернуть результат для 1 миллиона входов примерно за 10 секунд.

class Program
{
    static void Main(string[] args)
    {
        int T = Convert.ToInt32(Console.ReadLine());
        StringBuilder sb = new StringBuilder("");
        for (int i = 0; i < T; i++)
        {
            int N = Convert.ToInt32(Console.ReadLine());
            int[] numOfStairs = new int[N + 1];
            numOfStairs[0] = 0;
            int floorsMarked = 0;
            string[] str = Console.ReadLine().Split();
            for (int j = 0; j < str.Length; j++)
            {
                int length = Convert.ToInt32(str[j]);
                int reach = j + length > N ? N : j + length;
                while (floorsMarked < reach)
                {
                    floorsMarked++;
                    numOfStairs[floorsMarked] = numOfStairs[j] + 1;
                }
                if (reach >= N)
                    break;
            }
            int Q = Convert.ToInt32(Console.ReadLine());
            for (int j = 0; j < Q; j++)
            {
                int target = Convert.ToInt32(Console.ReadLine());
                sb.AppendLine(numOfStairs[target].ToString());
            }
        }
        Console.WriteLine(sb.ToString());
    }
}

Применил несколько незначительных оптимизаций к коду из ответа OP. Также исправлены проблемы с именованием (имя местных жителей начинается с буквы в нижнем регистре).

class Program
{
    static void Main(string[] args)
    {
        int t = int.Parse(Console.ReadLine());
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < t; i++)
        {
            int n = int.Parse(Console.ReadLine());
            int[] numOfStairs = new int[n];
            int floorsMarked = 0;
            string[] str = Console.ReadLine().Split();
            for (int j = 0; j < str.Length; j++)
            {
                int length = int.Parse(str[j]);
                int reach = j + length > n ? n : j + length;
                while (floorsMarked < reach)
                {
                    floorsMarked++;
                    numOfStairs[floorsMarked] = numOfStairs[j] + 1;
                }
                if (reach == n)
                    break;
            }
            int q = int.Parse(Console.ReadLine());
            for (int j = 0; j < q; j++)
            {
                int target = int.Parse(Console.ReadLine());
                sb.Append(numOfStairs[target]).AppendLine();
            }
        }
        Console.Write(sb);
    }
}