Раствор и оптимизация проблем алгоритма алгоритма летакодола лета

алгоритм

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

Без лишних слов, давайте к делу.

Алгоритм подъема по лестнице

Всем известно, что самое главное в алгоритме подъема по лестнице — это идея рекурсии, поэтому поговорим о рекурсии.

Что такое рекурсия?

  1. концепция

  • Функция прямо или косвенно вызывает себя в программе

  • позвони себе напрямую

  • называть себя косвенно

  • Выпрыгивай из конструкции, есть результат, когда выпрыгиваешь

  1. Мысль

  • Рекурсивный вызов в конечном итоге будет преобразован в собственную функцию.

  • Если есть функция fd, если это рекурсивная функция, то в итоге задача все равно преобразуется к виду функции fd

  • Идея рекурсии состоит в том, чтобы преобразовать неизвестную проблему в решаемую проблему для достижения

function fd(){
    ...fd()...
}

Разобравшись с рекурсией, давайте поговорим об алгоритме подъема по лестнице.

n ступеней лестницы

Во-первых, когда есть только одна лестница, очевидно, что есть только один путь; Когда есть две лестницы, также очевидно, что есть два пути. Будет следующее судебное решение

if (n == 1 || n == 2) {
        return n;
    }

Возникла идея первого порядка и второго порядка, а если порядок третьего порядка, четвертого порядка или даже n-порядка? В это время появляется идея рекурсии, Если порядок n, путь следующий:

   climbStairs(n - 2) + climbStairs(n - 1);

Болтать и болтать о нашем коде вышло

var climbStairs = function (n) {
    if (n == 1 || n == 2) {
        return n;
    }
    else {
        return climbStairs(n - 2) + climbStairs(n - 1);
    }
}

В настоящее время вы можете с радостью перейти на LeetCode, чтобы отправить код, и тогда вы найдете

???Что это за хрень?Я так много работал,чтобы напечатать код,ты делаешь это со мной?

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

function climbStairs(n){
    if (n == 1 || n == 2) 
        return n;

let ret = 0,
pre = 2,
prepre = 1;
for(let i = 3; i <= n ;i++){
    ret = pre + prepre;
    prepre = pre;
    pre =ret
}
return ret;
}

Суммировать

Когда я впервые столкнулся с проблемой подъема по лестнице, я сразу же подумал использовать для этого рекурсивный метод, а затем проверил некоторые знания о рекурсии. Затем я проанализировал проблему.Это частный случай, когда лестницы имеют только один порядок и два порядка.Полный код n-уровневой лестницы написан рекурсивно.Когда я пошел в LeetCode, чтобы отправить код, я понял проблему опять переполнение памяти.Оптимизация, и наконец-то написал этот код.

Категории