climb_stairs

  • 2022-12-14
  • 浏览 (515)

climb_stairs.go 源码

package main

//爬楼梯

//递归,指数级时间复杂度
//运行结果:超时
func climbStairs1(n int) int {
	if n <= 2 {
		return n
	}

	return climbStairs1(n-1) + climbStairs1(n-2)
}

//备忘录
var mem = map[int]int{}

func climbStairs2(n int) int {
	if n <= 2 {
		return n
	}

	if _, exist := mem[n]; exist {
		return mem[n]
	}
	res := climbStairs2(n-1) + climbStairs2(n-2)
	mem[n] = res
	return res
}

//动态规划的思想
func climbStairs3(n int) int {
	if n <= 2 {
		return n
	}

	prev, next := 1, 2
	for i := 2; i < n; i++ {
		prev, next = next, prev+next
	}
	return next
}

你可能感兴趣的文章

best_time_buy_sell_stock

best_time_buy_sell_stock_ii

container_with_most_water

0  赞