LeetCode #70 爬楼梯，如何加速我的解决方案？

Question

我在 LeetCode #70 爬楼梯上有解决这个问题，我的解决方案没有通过，因为它很慢...

我添加了一个使用 thunk 的蹦床，并且添加了 Memoization，我还可以添加什么来加快速度以实际通过我的代码下面这个问题的时间要求，在此先感谢。

LeetCode上的描述：

您正在爬楼梯。需要 n 步才能到达顶部。

每次您可以爬 1 或 2 个台阶。您可以通过多少种不同的方式登顶？

注：给定n为正整数。

Example 1:

Input: 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps


Example 2:

Input: 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step

Link LeetCode 上的问题：https://leetcode.com/problems/climbing-stairs/


let cache = {};

const sumStairSteps = arr => arr.reduce((acc, cur) => acc + cur, 0);

const thunk = (fn, ...args) => {
    return () => fn(...args);
}

const climbStairsHelper2 = fn => {

    let thunk = fn();

    while (typeof thunk === "function") {
        thunk = thunk();
    }

    return thunk;
};

const climbStairs2 = (newStairSequence, ladderCount) => {
    const sum = sumStairSteps(newStairSequence);

    if (sum === ladderCount) {  cache[ladderCount] = cache[ladderCount] + 1; }


    if (1 + sum <= ladderCount) {
        climbStairsHelper2(thunk(climbStairs2, [ ...newStairSequence, 1 ], ladderCount));
    }

    if (2 + sum <= ladderCount) {
         climbStairsHelper2(thunk(climbStairs2, [ ...newStairSequence, 2 ], ladderCount));
    }
};

const climbStairs = n => {
        if (n in cache) return cache[n];
        cache[n] = 0;
        climbStairs2([], n);
        console.log(cache[n]);
        return cache[n];
};

Answer 1

我不太理解你在这里使用的方法。这个问题实际上非常简单：编写朴素的递归解决方案，然后 memoize 结果。也就是说，如果您访问缓存中的楼梯，则 return 它，否则计算它。运行时间是线性的。

const climbStairs = (goal, curr=0, memo={}) => {
  if (goal < curr) {
    return 0;
  }
  else if (goal === curr) {
    return 1;
  }
  else if (curr in memo) {
    return memo[curr];
  }
  
  return memo[curr] = climbStairs(goal, curr + 1, memo) +
                      climbStairs(goal, curr + 2, memo);
};

console.log(climbStairs(50));

Answer 2

好的，所以您希望解决方案更加优化。

您当前讨论的解决方案具有线性运行时间，即 O(N) 并且在 LeetCode 上被接受。 现在我们先不谈 space 的复杂性。

这个问题和其中一类问题可以通过一种称为矩阵求幂的方法来解决，该方法具有对数运行时间，即 O(Log N)

矩阵求幂在这个 link

中有很好的描述

https://discuss.codechef.com/t/building-up-the-recurrence-matrix-to-compute-recurrences-in-o-logn-time/570

LeetCode #70 爬楼梯，如何加速我的解决方案？

LeetCode #70 Climbing Stairs, How to speed up my solution?

javascript

optimization

recursion

dynamic-programming

trampolines