这道题目和剑指offer中的青蛙跳台阶是一个问题。
题目描述
解题思路:动态规划
动态规划的核心思路在于:要想爬到第i个台阶就必须爬到第i-1个台阶和第i-2个台阶,所有的可能性就是这两种情况的和。
var climbStairs = function (n) { let dp = []; dp[0] = 0; dp[1] = 1; dp[2] = 2; for (let i = 3; i <= n; i++) { dp[i] = dp[i - 1] + dp[i - 2]; } return dp[n] }; 复制代码
题目反思
本题如果直接采用递归的方法,肯定是要超时的,动态规划是解决这类问题的好方法。 动态规划的关键在于准确的列出动态规划的方程。
作者:Always_positive
链接:https://juejin.cn/post/7013537908246183944
来源:稀土掘金
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。