LeetCode------递归(爬楼梯)

简介: 这篇文章通过LeetCode上的"爬楼梯"问题介绍了递归的基本概念和实现方法,包括递归公式的推导、基本递归实现、使用备忘录优化以避免重复计算,以及自底向上的迭代方法来提高效率。

1、递归

  • 1、一个问题的解可以分解为几个子问题的解。
  • 2、这个问题与分解之后的子问题,除了数据规模不同,求解思路完全一样
  • 3、存在基线/终止条件

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/climbing-stairs

题目
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?

注意:给定 n 是一个正整数。

示例 1:

输入: 2
输出: 2
解释: 有两种方法可以爬到楼顶。
1.  1 阶 + 1 阶
2.  2 阶

示例 2:

输入: 3
输出: 3
解释: 有三种方法可以爬到楼顶。
1.  1 阶 + 1 阶 + 1 阶
2.  1 阶 + 2 阶
3.  2 阶 + 1 阶

推导递归公式:
F(1) =1
F(2) =2
当n>=3时,第一次要么走一个台阶,然后剩余n-1个台阶要走。第一次走两个台阶,然后就要剩余n-2个台阶要走。
推导出递归公式
在这里插入图片描述

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

第一种代码实现

public int climbStairs(int n) {
        if(n == 1) return 1;
        if(n == 2) return 2;
      return climbStairs(n-1)+climbStairs(n-2);
      }

实现结果,时间超时
假如使用这种代码实现,从图中可以看出,每次都会重复计算已有的数据。怎样避免这种情况呢?可以将每次计算出来的结果存储起来,在计算之前先查询存储的数据是否存在。如果存在直接使用,不用再次计算。可以使用hashMap来存储计算的值

代码改进

 private Map<Integer,Integer> storeMap = new HashMap<>();
    public int climbStairs(int n) {
        if(n == 1) return 1;
        if(n == 2) return 2;
        if(null != storeMap.get(n)){
            return storeMap.get(n);
        }else{
            int result = climbStairs(n-1)+climbStairs(n-2);
            storeMap.put(n,result);
            return result;
        }

    }

另外一种解法,从下往上的形式
在这里插入图片描述
代码实现

 public int climbStairs(int n){
        if(n == 1) return 1;
        if(n == 2) return 2;
        int result = 0;
        int pre = 2;
        int prePre = 1;
        for(int i = 3;i<=n;i++){
            result = pre +prePre;
            prePre = pre;
            pre = result;
        }
        return result;
    }
相关文章
|
4月前
|
机器学习/深度学习 存储 算法
LeetCode 题目 95:从递归到动态规划实现 不同的二叉搜索树 II
LeetCode 题目 95:从递归到动态规划实现 不同的二叉搜索树 II
|
4月前
|
存储 算法 数据挖掘
python5种算法模拟螺旋、分层填充、递归、迭代、分治实现螺旋矩阵ll【力扣题59】
python5种算法模拟螺旋、分层填充、递归、迭代、分治实现螺旋矩阵ll【力扣题59】
|
4月前
|
机器学习/深度学习 存储 算法
Python5种算法回溯+剪枝、字典序、递归交换、计数回溯、迭代法 实现全排列ll【力扣题47】
Python5种算法回溯+剪枝、字典序、递归交换、计数回溯、迭代法 实现全排列ll【力扣题47】
|
4月前
|
存储 机器学习/深度学习 算法
python 五种算法转置后翻转、层次旋转、递归分块、一次性旋转、环状替换 实现旋转图像【力扣题48】
python 五种算法转置后翻转、层次旋转、递归分块、一次性旋转、环状替换 实现旋转图像【力扣题48】
|
4月前
|
存储 算法 数据可视化
力扣156题最全解法:如何上下翻转二叉树(递归与迭代方法详解,附图解)
力扣156题最全解法:如何上下翻转二叉树(递归与迭代方法详解,附图解)
|
4月前
|
存储 算法 数据可视化
LeetCode 题目 96:从动态规划、递归到卡塔兰数实现不同的二叉搜索树
LeetCode 题目 96:从动态规划、递归到卡塔兰数实现不同的二叉搜索树
|
4月前
|
存储 算法 数据可视化
LeetCode 131题详解:高效分割回文串的递归与动态规划方法
LeetCode 131题详解:高效分割回文串的递归与动态规划方法
|
4月前
|
SQL 算法 数据可视化
LeetCode题目92:反转链表ll 【python 递归与迭代方法全解析】
LeetCode题目92:反转链表ll 【python 递归与迭代方法全解析】
|
4月前
|
存储 传感器 算法
LeetCode题目89:格雷码 递归、迭代及位操作在数组合并中的应用
LeetCode题目89:格雷码 递归、迭代及位操作在数组合并中的应用
|
4月前
|
算法 数据可视化 数据挖掘
LeetCode题目104: 二叉树的最大深度(递归\迭代\层序遍历\尾递归优化\分治法实现 )
LeetCode题目104: 二叉树的最大深度(递归\迭代\层序遍历\尾递归优化\分治法实现 )
LeetCode题目104: 二叉树的最大深度(递归\迭代\层序遍历\尾递归优化\分治法实现 )