此网站主题为本人手写主题, 主题待开源···
题目:一个长阶梯有n级,可以一次走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);
}
评论区