常州网站建设书生商友,临沂做网站找哪家好,中国进出口贸易平台,网址短链接生成题意理解#xff1a; 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。其中每次只能爬1阶或2阶。 问#xff1a;爬到楼顶有几种走法#xff1f; 如: n1 爬一阶#xff1a; 1 n2 爬两阶#xff1a; 11 要么从第1阶再爬一阶#xff0c;要么从第0阶#xff0c;一次性爬两阶… 题意理解 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。其中每次只能爬1阶或2阶。 问爬到楼顶有几种走法 如: n1 爬一阶 1 n2 爬两阶 11 要么从第1阶再爬一阶要么从第0阶一次性爬两阶 n3 爬三界 12 11)1 21 要么从第2阶再爬一阶即可要么在第1阶一次性爬两阶即可 而爬到第1阶有一种方式爬到第2阶有两种方式 故爬到第三阶有123种方式 则有递推公式f[i]f[i-1]f[i-2] 解题思路 采用动态规划的方式求解此题按照五个步骤来分析。 1. 确定dp[]数组和下标的含义其中dp[i]表示爬到第i阶有几种方式。 2. 确定递归函数dp[i]dp[i-1]dp[i-2] 3. 初始化dp[1]1 dp[2]2 4. 确定遍历方式总是前面的结果影响后续取值所以遍历顺序总是从前到后 5.打印dp数组用于debug 1.动态规划解题 public int climbStairs(int n) {//定义存储int[] dpnew int[n1];//初始化dp[1]1;if(n1) dp[2]2;//遍历for(int i3;in;i){dp[i]dp[i-1]dp[i-2];}return dp[n];}
2.存储压缩
使用数值取代数组存储结果。空间复杂度O(n1)——O(3)
public int climbStairs(int n) {//定义存储int sum0,dp11,dp22;if(n1) return dp1;if(n2) return dp2;//初始化sumdp1dp2;//遍历for(int i3;in;i){sumdp1dp2;dp1dp2;dp2sum;}return sum;}
3.分析 时间复杂度O(n) 用于遍历n个状态值 空间复杂度 数组存储 O(n) 数值存储 O(1) n表示输入的数值的大小。
