爬楼梯——动态规划第一步

本文主要是介绍爬楼梯——动态规划第一步，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

本问题其实常规解法可以分成多个子问题，爬第 n 阶楼梯的方法数量，等于两个部分之和

1. 爬上 n−1 阶楼梯的方法数量。因为再爬 1 阶就能到第 n 阶
2. 爬上 n−2 阶楼梯的方法数量，因为再爬 2 阶就能到第 n 阶

所以我们得到公式 dp[n] = dp[n−1] + dp[n−2]
初始化 dp[0]=1 和 dp[1]=1
时间复杂度：O(n)

class Solution {public int climbStairs(int n) {int[] dp = new int[n+1];dp[0] = 1;dp[1] = 1;for(int i = 2; i <= n; i++){dp[i] = dp[i-1] + dp[i-2];}return dp[n];}
}

最近做动态规划的题目，发现最重要的还是要能够拿着笔一步一步模拟，才能真正搞懂步骤

这篇关于爬楼梯——动态规划第一步的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---