восхождение по лестнице - ограничение между двумя решениями - PullRequest
Новая
       15

восхождение по лестнице - ограничение между двумя решениями

0 голосов
/ 24 мая 2018

При работе с лестницей Leetcode 70: Вы поднимаетесь по лестнице.Чтобы добраться до вершины, нужно сделать n шагов. Каждый раз вы можете подняться на 1 или 2 шага.Во сколько разных способов вы можете подняться на вершину?Вот мое первое решение: 

class Solution {

    public int fib (int n){
        if (n <= 2) return n;
        return fib(n-1) + fib(n-2);
    }

    public int climbStairs(int n) {
        return fib (n+1);

    }
}

, когда n <44, это работает, но n> = 44, это не работает. Из-за этого это приводит к ошибке при отправке в leetcode.но при использовании 2-го решения, показанного ниже 

class Solution {
    public int climbStairs(int n) {
        if (n <= 2) return n;
        int[] allWays = new int[n];
        allWays[0] = 1;
        allWays[1] = 2;
        for (int i = 2; i < n; i++){
            allWays[i] = allWays[i-1] + allWays[i-2];
        }
        return allWays[n-1];
    }
}

, второе решение принимается с помощью leetcode.однако, когда n> = 46, это дает отрицательное число.

Может кто-нибудь дать мне какое-то объяснение, почему первое решение не удается?в чем разница между двумя решениями?Спасибо.

Ответы [ 2 ]

0 голосов
/ 24 мая 2018

Ваша интуиция верна.Количество способов достичь вершины действительно следует последовательности Фибоначчи.

Первое решение вычисляет числа Фибоначчи рекурсивно (fib(n) = fib(n - 1) + fib(n-2)).Чтобы вычислить любое значение, функция должна рекурсивно вызывать себя дважды.Каждый вызов функции занимает место в области памяти, называемой стеком.Вероятно, это происходит, когда n слишком велико, происходит слишком много рекурсивных вызовов, и программе не хватает места для выполнения большего количества вызовов.

Второе решение использует динамическое программирование и запоминание.Это эффективно экономит пространство и время вычислений.Если вы не знаете этих тем, я бы посоветовал вам прочитать их.

Вы получаете отрицательные значения, поскольку 47-е число Фибоначчи больше максимального значения, которое может быть представлено типом int.Вы можете попробовать использовать long или BigInteger класс для представления больших значений.

0 голосов
/ 24 мая 2018

Чтобы понять решение, вам нужно понять концепцию Dynamic Programming и Recursion

В первом решении для вычисления n-го числа Фибоначчи ваш алгоритм равен

fib(n)= fib(n-1)+fib(n-2)

Но второе решение более оптимизировано. Этот подход сохраняет значения в массиве, так что вам не нужно каждый раз вычислять fib(n).

Пример: 

fib(5) = fib(4) + fib(3)
       = (fib(3) + fib(2)) + (fib(2) + fib(1))

По первому решению вы рассчитываете fib (2) дважды для n = 4.

По второму решению вы сохраняете значения Фибоначчи в массиве

Пример: для n = 4,

сначала вы вычисляете fib(2) = fib(1)+fib(0) = 1
затем вы вычисляете f(3) = f(2)+f(1) Нам не нужно вычислять the fib(2), так как оно уже сохранено в массиве.

Проверьте эту ссылку для более подробной информации

...