爬楼梯算法题

爬楼梯算法题

科技前沿 • 2025-02-27 20:13 • 阅读 30

大家好，我是讯享网，很高兴认识大家。

爬楼梯算法题：

思路和算法：

典型的动态规划问题

我们用 f(x)表示爬到第 x 级台阶的方案数，
考虑最后一步可能跨了一级台阶，也可能跨了两级台阶，所以我们可以列出如下式子： f(i)=f(i−1)+f(i−2).

讯享网

我们可以用「滚动数组思想」来理解，如图所示。
在这里插入图片描述

总结动态规划解题思路

什么样的问题可以使用动态规划？ 一个问题能用动态规划来解决，需要满足： - 可分解：问题可以被分解为更小的子问题来求解。以此题为例：要走到第i阶，可以由第i-1阶走一步、第i-2阶走两步实现，所以走到第i阶的路径数 = 走到第i-1阶的路径数 + 走到第i-2阶的路径数，也就是说我们将大小为i的问题，分解为了大小为i-1和i-2的子问题，而大小为i-1的子问题可以进一步被分解到更小的子问题，直到小到可以显然求解（大小为0或者1）为止。 - 无后效性：未来的状态与过去无关。在本题中：任意一条走到i-1或者i-2的路径都提供了一条到达i的路径，不论这条路径是如何走的，对这个结果都没有影响。 - 最优子结构：一个问题的最优解由子问题的最优解得到。在本题中：最优解其实是全部路径，也就是i的全部路径数是由i-1和i-2的路径数得到的。

讯享网

讯享网对于动态规划问题，我将拆解为如下五步曲，这五步都搞清楚了，才能说把动态规划真的掌握了！ 理解函数表达式以及下标的含义 确定递推公式 函数值如何初始化 确定遍历顺序 举例推导

代码：

/ * Created by Martin on 2021/9/2 17:12 * * 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 * 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？ */ /* * 思路和算法 我们用 f(x)表示爬到第 x 级台阶的方案数， * 考虑最后一步可能跨了一级台阶，也可能跨了两级台阶，所以我们可以列出如下式子： * f(x)=f(x−1)+f(x−2) * * */ public class demo { 
    public static void main(String[] args) { 
    int i = climbStairs(4); System.out.println(i); } public static int climbStairs(int n) { 
    if(n == 1) return 1; if(n == 2) return 2; int[] climb = new int[n + 1]; climb[1] = 1; climb[2] = 2; for(int i = 3; i <= n; i++){ 
    climb[i] = climb[i - 1] + climb[i - 2]; } return climb[n]; } }

欢迎点赞关注收藏
在这里插入图片描述

爬楼梯算法题：

思路和算法 ：

总结动态规划解题思路

代码：

相关推荐

思路和算法：