空间复杂度为 O(1) 的动态规划

上模版

• 递推公式: f(n) = f(n-1) + f(n-2)
• 递归退出条件:

    f(0) == 0
    f(1) == 1
    f(2) == 2
  即:
  if numbers < 3:
    return numbers

• 转化为动态规划: 只需要 3 个变量

  # n >= 3
  # 答案, f(n-2), f(n-1)
  ans, f2, f1 = 0, 1, 2
  for index in range(3, numbers+1):
    ans = f1 + f2
    # 更新 f(n-1), f(n-2)
    f1, f2 = ans, f1

完整代码
Python3 实现

class Solution:
    def jumpFloor(self, number):
        if number < 3:
            return number
        # 答案, f(3-2), f(3-1)
        ans, f2, f1 = 0, 1, 2
        for i in range(3, number+1):
            ans = f1 + f2
            # 更新 f(n-1), f(n-2)
            f1, f2 = ans, f1
        return ans

Golang 实现

package main

/**
 * 
 * @param number int整型 
 * @return int整型
*/
func jumpFloor( number int ) int {
    if number < 3 {
        return number
    }
    var ans, f2, f1 int = 0, 1, 2
    for i:= 3; i <= number; i++ {
        ans = f1 + f2
        f1, f2 = ans, f1
    }
    return ans
}