Я решаю проблему с рекурсией, но в моем последнем тестовом примере возникла ошибка Tle. Как мне оптимизировать код?

Question

Вот мой вопрос:

Учитывая массив неотрицательных целых чисел, вы изначально располагаетесь в первом индексе массива.

Каждый элемент в массиве представляет ваш максимальный прыжок длина в этой позиции.

Определите, можете ли вы достичь последнего индекса.

А вот мой код:

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int index=nums.size()-1;
        bool ans=dfs(nums,0);
        return ans;
    }
    bool dfs(vector<int>&nums,int start)
    {
        if(start>=0 && start<nums.size())
        {
            if(start == nums.size()-1)
            {
                return true;
            }
            if(nums[start] == 0)
            {
                return false;
            }
            else if(start>=nums.size())
            {
                return false;
            }
            for(int i=1;i<=nums[start];i++)
            {
                bool check = dfs(nums,start+i);
                if(check == true)
                {
                    return true;
                }
            }
        }
        return false;
    }
};

Однако я получил ответ на последнем тесте case: Вот последний тестовый пример

Как я могу оптимизировать свой код? Пожалуйста, помогите

Спасибо.

Answer 1

Я могу что-то неправильно понять, но это кажется очень простым для решения с помощью одной итерации по массиву (от конца до начала).

• Если вы знаете этот индекс i может дойти до конца, и вы обнаружите, что вы можете достичь индекса i из индекса c, тогда индекс c также может достичь конца.

• Если вы можете прыгнуть до n шагов, имеют индекс c и знают i <= c + n, тогда вы можете достичь индекса i.

• Если индекс i и индекс j может доходить до конца и i < j, тогда достаточно, если вы дойдете до i.

bool CanReachEnd(std::vector<int> const & jumps)
{
    assert(jumps.size() > 0);
    std::size_t current = jumps.size() - 1;
    std::size_t lowest_can_reach_end = current;
    while (true)
    {
        assert(jumps[current] >= 0); // "non negative", unsigned would be better!
        if (current + jumps[current] >= lowest_can_reach_end)
        {
            lowest_can_reach_end = current;
        }
        if (current == 0) break;
        current -= 1;
    }
    assert(current == 0);
    return (lowest_can_reach_end == 0);
}

(Демо)

Answer 2

По сути, это N <= 10^5, что означает, что вы должны найти решение O(n*log(n)) для этого. Ваш DFS может быть тривиально уменьшен до O(N^2), если вы его мемоизируете, но он значительно медленнее в своем текущем немемоизированном состоянии. Идея заключается в том, что вы можете использовать структуру данных, такую ​​как дерево Фенвика (также известное как двоичное индексированное дерево или BIT), для хранения, если позиция может достигнуть конца или нет. Затем вы можете получить сумму диапазона в O(log(n)) и также обновить элемент в O(log(n)). Затем вы можете определить входной массив как nums, массив, содержащий, может ли индекс быть poss, и сумму poss[x] от i до j (включая j, но не i) должно быть sum(poss, i, j). Вы можете рассчитать poss по следующей формуле:

poss[n - 1] = 1
poss[i] = max(1, sum(poss, i, min(i + nums[i], n - 1)))