I want reduce the time complexity for this ladder problem to find the minimum ladders required

Question

I was trying to attempt below given challenge. I tried multiple ways to solve the problem but none of them were good enough to pass the time limit. Please advise if you have any idea to improve on this.

Problem: You are visiting a building of N floors. On every floor, only one ladder of specified length is present. If the length of the ladder is x units, you can reach y floors above from the current one.

You can leave the ladder in between in order to change the ladder, but you can only start from the starting floor of the ladder.

You are given Q questions. In each question, you will be given a floor number. For each question, you have to tell the least number of ladders required to reach given floor. Initially, you are on the ground floor.

Input Format: The first line contains an integer T, indicating the number of test cases. For each test case: The first line contains an integer N, indicating number of floors in the building. Next line contains N space separated positive integers which denote the length of ladder at each floor (First integer corresponds to ladder length on ground floor, second integer corresponds to ladder length on first floor and so on) . Next line contains an integer Q, indicating number of questions. Following Q lines contain an integer each, denoting the floor number for which answer is to be computed.

Output Format: For each question, print the least number of ladders required required to reach given floor. Answer for each question should come in a new line.

Sample Input:

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

Sample Output:

4
3
2
1
1
6
5
5
5
4

Problem Reference

Solution:

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

Answer 1

Applied few minor optimisations to the code from the OP's answer. Also fixed naming issues (locals name starts from a lower-cased letter).

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 + 1];
            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);
    }
}

Answer 2

I was finally able to reduce it enough to return result for 1 million inputs in around 10 secs.

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