公告栏

此网站主题为本人手写主题, 主题待开源···

音乐盒

站点信息

文章总数目: 307
已运行时间: 1166
目录
尼采般地抒情

尼采般地抒情

尼采般地抒情

公告栏

此网站主题为本人手写主题, 主题待开源···

站点信息

文章总数目: 307
已运行时间: 1166

题目:一个长阶梯有n级,可以一次走1级,一次走2级,一共有多少种走法?

经典的动态规划问题,从结果来看:

  • 到达第n层阶梯的方式只有两种,走一步然后结束,或者走两步然后结束。
  • 到达第n-1层阶梯的方式只有两种,走一步然后结束,或者走两步然后结束。
  • ……

抽离于动态规划模型,动态规划解题主要是解决两点(一般难题也就从这两个点来设置)

  1. 动态方程
  2. 边界条件

let arr = new Array(n).fill(0)

// 边界条件
arr[0] = 1
arr[1] = 2

for (let i = 2; i<arr.length; i++) {
  // 动态方程
  arr[i] = arr[i-1] + arr[i-2]
}

console.log(arr[n-1])


还可以用递归(不建议用,复杂度太高指数级,但是因为和递归看起来有点像,所以写出来作为比较)

let jie = n => {
  if(n === 1) return 1;
  if(n === 2) return 2;
  if(n > 2)  return jie(n-1) + jie(n-2);
}

评论区

Twikoo giscus