1 题目再现小明正在爬楼梯一次要么上升1个台阶要么上升2个台阶问小明爬台阶个数为n的楼梯一共有多少种方法输入楼梯台阶总数n输出爬n层台阶一共多少种方法2 解题思路方法1递归实现经典递归问题首先考虑n从1开始一共多少种方法作为递归的出口n1时输出1因为楼梯台阶数为1小明一次要么上升1个台阶要么上升2个台阶所以只有一种方法爬到终点。if(n1) return 1;n2时输出2两种方法。方法1一次爬1阶一共爬两次 方法2一次爬2阶一共爬一次if(n2) return 2;再回到要解决的问题问的是爬n层台阶一共有多少种方法只知道小明一次要么上升一个台阶或者两个台阶。如果顺着思考就会觉得问题很困难需要分好几种情况讨论但是这也是一种方法叫迭代下面接着讨论就像树的分支一样越分树枝越多。如果逆着思考也就是从最后一步看倒数第二步只有两种可能一种是从倒数第二步n-2层台阶跨两级台阶到达终点另一种n-1层台阶跨一级台阶到达终点。return solution(n-1)solution(n-2);每一层思考方式都是这样倒着推内部逻辑函数一样就可以调用函数自己再来一遍也就是递归。但是每次递归都是再传入n-1和n-2再去求需要有最终的出口最终的出口就是n1时返回1一层台阶只有一种方法n2时返回2两层台阶有两种方法递归实现完整代码Javaimport java.util.Scanner; public class Main { public int Solution(int n){ if(n1)return 1; if(n2)return 2; return Solution(n-1)Solution(n-2); } public static void main(String[] args) { Main mainnew Main(); Scanner scannew Scanner(System.in); int n scan.nextInt(); System.out.println(main.Solution(n)); } }加入输入台阶数为4求方法数正确为5共5种爬该4层楼梯的方法实际输出与预期一致方法2迭代实现递归实现是从结果倒着推利用函数自身的逻辑再循环内求直到源点n1和n2的情况。但是这种简单的逻辑几行代码往往里面会有潜在的资源浪费比如重复计算仔细拆解就可发现如下图所示如图,在求爬5层台阶一共需要多少种方法的时候一般先从结果倒着推然后往下每一个子树内部处理逻辑都是和最大的从5层开始倒退的逻辑是一样的这也就造成了每一部分函数递归又重新进行了一遍计算就比如f(3)在从5倒着推的时候就已经计算一遍了但是在4层倒着推的时候因为和兄弟节点中的f(3)独立没法利用已经计算好的f(3)只能再重新计算一遍就会造成资源浪费。f(5) / \ f(4) f(3) / \ / \ f(3) f(2) f(2) f(1) / \ f(2) f(1)那怎么才能不造成资源浪费最简单的方法就是每个计算好的f(N)都存储起来下次再用不用重复计算直接把原先的值拿过来就行。这显然是递归这种从结果往前推每一步都需要再通过源点这头的元素计算无法实现的。实现这种每个计算好的节点存储起来只能通过从源点推结尾一步一步的计算存储、计算存储。也就是说从已知的、最简单的情况开始顺着往上算而不是从 n 往回拆。递归是从上往下拆问题 → 遇到边界再回溯计算。迭代是从下往上推结果 → 用前面算好的结果直接算后面的。因为每一步 f (i) 只依赖 f (i-1) 和 f (i-2)我们完全不需要把所有结果都存起来只需要记住最近两个值不断往后推就行。迭代思路顺着爬楼梯从低到高我们已经明确台阶数为 1只有 1 种走法即 f (1) 1台阶数为 2只有 2 种走法即 f (2) 2台阶数为 3 时最后一步要么从 2 级走 1 步要么从 1 级走 2 步。所以f (3) f (2) f (1)台阶数为 4 时f (4) f (3) f (2)以此类推f(n) f(n-1) f(n-2)迭代就是从 1、2 开始一步步算出 3 → 4 → 5 → … → n每一个数只算一次没有任何重复计算。迭代实现完整代码Java我们定义三个变量prePre表示 f (n-2)一开始存 f (1) 1pre表示 f (n-1)一开始存 f (2) 2res表示当前算出的 f (n)import java.util.Scanner; public class Main { public int Solution(int n) { if (n 1) return 1; if (n 2) return 2; // 最开始已知 f(1)1f(2)2 int prePre 1; int pre 2; int res 0; // 从第3级开始一直算到第n级 for (int i 3; i n; i) { // 当前台阶方法数 前1个 前2个 res prePre pre; // 变量往后滚动为下一次循环做准备 prePre pre; pre res; } return res; } public static void main(String[] args) { Main main new Main(); Scanner scan new Scanner(System.in); int n scan.nextInt(); System.out.println(main.Solution(n)); scan.close(); } }关键三行代码解释非常重要java运行res prePre pre; // 算出当前台阶的方法数 prePre pre; // prePre 向后挪一位变成原来的 pre pre res; // pre 向后挪一位变成刚算出来的结果第一次循环i3prePre f (1)pre f (2)res f (1)f (2) f (3)第二次循环i4prePre 变成 f (2)pre 变成 f (3)res f (2)f (3) f (4)每循环一次就往上走一级台阶只用到 3 个变量不重复计算效率极高
编程入门算法题---小明爬楼梯求爬n层台阶一共多少种方法
1 题目再现小明正在爬楼梯一次要么上升1个台阶要么上升2个台阶问小明爬台阶个数为n的楼梯一共有多少种方法输入楼梯台阶总数n输出爬n层台阶一共多少种方法2 解题思路方法1递归实现经典递归问题首先考虑n从1开始一共多少种方法作为递归的出口n1时输出1因为楼梯台阶数为1小明一次要么上升1个台阶要么上升2个台阶所以只有一种方法爬到终点。if(n1) return 1;n2时输出2两种方法。方法1一次爬1阶一共爬两次 方法2一次爬2阶一共爬一次if(n2) return 2;再回到要解决的问题问的是爬n层台阶一共有多少种方法只知道小明一次要么上升一个台阶或者两个台阶。如果顺着思考就会觉得问题很困难需要分好几种情况讨论但是这也是一种方法叫迭代下面接着讨论就像树的分支一样越分树枝越多。如果逆着思考也就是从最后一步看倒数第二步只有两种可能一种是从倒数第二步n-2层台阶跨两级台阶到达终点另一种n-1层台阶跨一级台阶到达终点。return solution(n-1)solution(n-2);每一层思考方式都是这样倒着推内部逻辑函数一样就可以调用函数自己再来一遍也就是递归。但是每次递归都是再传入n-1和n-2再去求需要有最终的出口最终的出口就是n1时返回1一层台阶只有一种方法n2时返回2两层台阶有两种方法递归实现完整代码Javaimport java.util.Scanner; public class Main { public int Solution(int n){ if(n1)return 1; if(n2)return 2; return Solution(n-1)Solution(n-2); } public static void main(String[] args) { Main mainnew Main(); Scanner scannew Scanner(System.in); int n scan.nextInt(); System.out.println(main.Solution(n)); } }加入输入台阶数为4求方法数正确为5共5种爬该4层楼梯的方法实际输出与预期一致方法2迭代实现递归实现是从结果倒着推利用函数自身的逻辑再循环内求直到源点n1和n2的情况。但是这种简单的逻辑几行代码往往里面会有潜在的资源浪费比如重复计算仔细拆解就可发现如下图所示如图,在求爬5层台阶一共需要多少种方法的时候一般先从结果倒着推然后往下每一个子树内部处理逻辑都是和最大的从5层开始倒退的逻辑是一样的这也就造成了每一部分函数递归又重新进行了一遍计算就比如f(3)在从5倒着推的时候就已经计算一遍了但是在4层倒着推的时候因为和兄弟节点中的f(3)独立没法利用已经计算好的f(3)只能再重新计算一遍就会造成资源浪费。f(5) / \ f(4) f(3) / \ / \ f(3) f(2) f(2) f(1) / \ f(2) f(1)那怎么才能不造成资源浪费最简单的方法就是每个计算好的f(N)都存储起来下次再用不用重复计算直接把原先的值拿过来就行。这显然是递归这种从结果往前推每一步都需要再通过源点这头的元素计算无法实现的。实现这种每个计算好的节点存储起来只能通过从源点推结尾一步一步的计算存储、计算存储。也就是说从已知的、最简单的情况开始顺着往上算而不是从 n 往回拆。递归是从上往下拆问题 → 遇到边界再回溯计算。迭代是从下往上推结果 → 用前面算好的结果直接算后面的。因为每一步 f (i) 只依赖 f (i-1) 和 f (i-2)我们完全不需要把所有结果都存起来只需要记住最近两个值不断往后推就行。迭代思路顺着爬楼梯从低到高我们已经明确台阶数为 1只有 1 种走法即 f (1) 1台阶数为 2只有 2 种走法即 f (2) 2台阶数为 3 时最后一步要么从 2 级走 1 步要么从 1 级走 2 步。所以f (3) f (2) f (1)台阶数为 4 时f (4) f (3) f (2)以此类推f(n) f(n-1) f(n-2)迭代就是从 1、2 开始一步步算出 3 → 4 → 5 → … → n每一个数只算一次没有任何重复计算。迭代实现完整代码Java我们定义三个变量prePre表示 f (n-2)一开始存 f (1) 1pre表示 f (n-1)一开始存 f (2) 2res表示当前算出的 f (n)import java.util.Scanner; public class Main { public int Solution(int n) { if (n 1) return 1; if (n 2) return 2; // 最开始已知 f(1)1f(2)2 int prePre 1; int pre 2; int res 0; // 从第3级开始一直算到第n级 for (int i 3; i n; i) { // 当前台阶方法数 前1个 前2个 res prePre pre; // 变量往后滚动为下一次循环做准备 prePre pre; pre res; } return res; } public static void main(String[] args) { Main main new Main(); Scanner scan new Scanner(System.in); int n scan.nextInt(); System.out.println(main.Solution(n)); scan.close(); } }关键三行代码解释非常重要java运行res prePre pre; // 算出当前台阶的方法数 prePre pre; // prePre 向后挪一位变成原来的 pre pre res; // pre 向后挪一位变成刚算出来的结果第一次循环i3prePre f (1)pre f (2)res f (1)f (2) f (3)第二次循环i4prePre 变成 f (2)pre 变成 f (3)res f (2)f (3) f (4)每循环一次就往上走一级台阶只用到 3 个变量不重复计算效率极高
