前端的网站重构怎么做,做网站用的编程语言,高端网站改版,服务好 售后好的网站制作在本题目中#xff0c;要求爬第n阶有多少种爬法#xff0c;并且每次只能爬1个或者2个#xff0c;这明显是动态规划的问题#xff0c;我们需要用动态规划的解决方式去处理问题。动态规划就是按照正常的顺序由前向后依次推导。而递归则是从结果往前去寻找#xff08;个人理解… 在本题目中要求爬第n阶有多少种爬法并且每次只能爬1个或者2个这明显是动态规划的问题我们需要用动态规划的解决方式去处理问题。动态规划就是按照正常的顺序由前向后依次推导。而递归则是从结果往前去寻找个人理解。
动态规划一共需要仔细处理5步
确定dp数组的含义以及其下标的含义dp数组一般保存的就是整个变化过程中一直变化的状态。确定递推公式。确定dp数组的初始化确定遍历顺序打印dp数组
所以我们根据这个题目先正常推导一下流程 当位于0层时假设为1 当位于1层时只有1种方法 当位于2层时有2种方法1层时往上走1个台阶即可 当位于3层时有3种方法1层时往上走两次1个台阶/2个台阶2层时往上走一个台阶
首先 我们确定dp数组的含义dp[i]表示爬到第i阶有多少种爬法 由上述推导可知dp[i] dp[i-1]dp[i-2] 我们初始化数组令dp[0]1dp[1]1(其实dp[0]1是整个数组种的特殊项好比数列种的特殊项) 之后我们从前向后依次推理就可以了
class Solution {public int climbStairs(int n) {int[] dp new int[n1];dp[0]1;dp[1]1;for(int i 2;in;i){dp[i] dp[i-1]dp[i-2];}return dp[n];}
}
