com网站建设,网站运行速度慢,wordpress获取文章所有标签,直播app开发需要多少钱【力扣】70. 爬楼梯
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢#xff1f;
示例 1#xff1a; 输入#xff1a;n 2 输出#xff1a;2 解释#xff1a;有两种方法可以爬到楼顶。
1. 1 阶 1 阶
2. …【力扣】70. 爬楼梯
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢
示例 1 输入n 2 输出2 解释有两种方法可以爬到楼顶。
1. 1 阶 1 阶
2. 2 阶示例 2 输入n 3 输出3 解释有三种方法可以爬到楼顶。
1. 1 阶 1 阶 1 阶
2. 1 阶 2 阶
3. 2 阶 1 阶提示 1 n 45
题解
确定 dp 数组以及下标的含义 dp[i] 的定义为爬到第 i 层楼梯有 dp[i] 种方法确定递推公式 状态转移方程 dp[i] dp[i - 1] dp[i - 2];dp 数组如何初始化 dp[1] 1dp[2] 2不考虑 dp[0] 如何初始化确定遍历顺序 从前向后遍历举例推导 dp 数组打印 dp 数组 N 为5的时候dp 数组应该是数列1 2 3 5 8 下标从1开始
public int climbStairs(int n) {int[] dp new int[n 1];if (n 1) {return n;}dp[1] 1;dp[2] 2;for (int i 3; i n; i) {dp[i] dp[i - 1] dp[i - 2];}return dp[n];
}变量代替数组 public int climbStairs(int n) {if(n 2) {return n;}int a 1, b 2, sum 0;for(int i 3; i n; i){sum a b; // f(i - 1) f(i - 2)a b; // 记录f(i - 1)即下一轮的f(i - 2)b sum; // 记录f(i)即下一轮的f(i - 1)}return b;}
