70. Stair climbing, DP traversal, variable caching results, JavaScript, detailed comments

Original link: leetcode-cn.com/problems/cl…

Answer:

The Fibonacci sequence can be solved by recursion to dynamic programming. The following is the traversal of dynamic programming, using variables instead of array cache.

/ * * *@param {number} n
 * @return {number}* /
var climbStairs = function (n) {
  let current = 0; // Store the current value, that is, the value of n
  let prev1 = 1; // Store the value of n-1
  let prev2 = 0; // Store the value of n-2

  F (n)=f(n-1)+f(n-2)
  for (let i = 1; i < n + 1; i++) {
    current = prev1 + prev2; // f(n)=f(n-1)+f(n-2)
    prev2 = prev1; // Save the value of n-2
    prev1 = current; // Save the value of n-1
  }

  return current;
};
Copy the code