Массив мин прыжков (подход сверху вниз) - PullRequest
Новая
       76

Массив мин прыжков (подход сверху вниз)

0 голосов
/ 22 марта 2020

Постановка задачи: Учитывая массив неотрицательных целых чисел A длиной N, вы изначально позиционируетесь в первом индексе массива. Каждый элемент в массиве представляет вашу максимальную длину прыжка в этой позиции. Возвращает минимальное количество прыжков, необходимое для достижения последнего индекса.

Ввод: A = [2,3,1,1,4]

Ввод: 2

Пояснение : Кратчайший путь к индексу 4 - это Индекс 0 -> Индекс 1 -> Индекс 4, требующий 2 скачка.

Ниже приведено решение: 

// M is the function that gives the required minimum jumps
// nums is the vector containing jumps (here I have used nums in place of array A).
// start denoting the starting index
// map(m) STL for memoization

int M(vector<int> &nums, int start, unordered_map<int, int>&m){

    if(start == nums.size()-1){return 0;} // if we reach the last index then return 0.

    if(start >= nums.size()){return INT_MAX;} // if we reach beyond last index then return some big value that can't be the answer.

    if(nums[start] == 0){return INT_MAX;} // if in mid we get jump value = 0 then we cannot expect the min jump so again return some big value.

    if(m[start] != 0){return m[start];} // if we already stored the value (calculated the answer) then return stored value 

    int ans = INT_MAX; // assuming initially answer to be some big value. 

    for(int i=1; i<=nums[start]; i++){ // jump can be made from 1 to maximum value of that element in array i.e. nums[start]

        ans = min(ans, 1+M(nums, start+i, m)); // answer is minimum of previously calculated answer and 1 + allowed path (start + i).

        m[start] = ans; // storing it in map.
    }

    return m[start]; // returning the stored value
}

Я получаю TLE для вышеуказанное решение. Я не могу выяснить временную сложность решения после запоминания. Может ли кто-нибудь помочь мне оценить временную сложность вышеуказанного решения.

Ответы [ 2 ]

0 голосов
/ 22 марта 2020

Не уверен в вашем вопросе, но я думаю, что у меня есть решение O (N): 

int M(const vector<int> &nums)
{
    int n_jumps = 0;
    int cur_pos = 0;
    int prev_pos = 0;
    int next_jump = 0;
    int max_value = 0;
    int value;
    int i;
    while (cur_pos + nums[cur_pos] < nums.size() - 1)
    {
        next_jump = 0;
        max_value = 0;
        i = cur_pos > 0 ? prev_pos + nums[prev_pos] + 1 : 1;
        for (; i <= cur_pos + nums[cur_pos]; ++i)
        {
            value = i + nums[i];
            if (value >= nums.size() - 1) return n_jumps + 2;
            if (max_value < value)
            {
                max_value = value;
                next_jump = i - cur_pos;
            }
        }
        prev_pos = cur_pos;
        cur_pos += next_jump;
        ++n_jumps;
    }
    return n_jumps + 1;
}

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

Обратите внимание, что при переходе к следующему элементу нам не нужно проверять доступные элементы с предыдущей позиции (что дает нам O (N)).

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

0 голосов
/ 22 марта 2020

У меня есть подход для решения этого вопроса в сложности O(nlogn) (возможно, были бы более подходящие подходы)

Использование ленивого дерева сегментов для хранения минимального значения для l,r индекса.

Для каждого набора индексов dp[i] = query(i,i), а затем update(i+1,dp[i]+i,dp[i]+1)

Если вы не уверены, оставьте комментарий. Я также предоставлю реализацию.

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

...