德阳网站建设公司哪家好,做游戏网站需要哪些许可,wordpress登录的图片不显示,六安城市网官网爬楼梯#xff0c;每次只能爬一阶或者两阶#xff0c;计算有多少种爬楼的情况 爬楼梯--题目描述暴力递归递归缓存动态规划暴力递归到动态规划专题 爬楼梯–题目描述 一个总共N 阶的楼梯#xff08;N 0#xff09; 每次只能上一阶或者两阶。问总共有多少种爬楼方式。 示… 爬楼梯每次只能爬一阶或者两阶计算有多少种爬楼的情况 爬楼梯--题目描述暴力递归递归缓存动态规划暴力递归到动态规划专题 爬楼梯–题目描述 一个总共N 阶的楼梯N 0 每次只能上一阶或者两阶。问总共有多少种爬楼方式。 示例1 N 1 一步上去了返回1. 示例2 N 2时。 可以第一次上一阶再上一阶这是一种方式 也可以一次直接上两阶这也是一种方式 返回 2 示例3 N 3 可以选择 1 1 1 1 2 2 1 三种方式上楼 返回3. 暴力递归 解题思路 先确认base case: 只有一层台阶时 有1种方式 只有两层台阶时 有两种方式 当N 层台阶时 当前这一步能选择上一层或者上两层两种可能性 因此f(N) f(N - 1) f(N - 2) 代码已经呼之欲出了 代码演示 /*** 暴力递归。* param N* return*/public static int paLouTi(int N){if (N 0){return 0;}return process(N);}/*** N层测楼梯 每次只能上一步或者两步* 总共有多少种爬楼的方式。* param N*/public static int process(int N){//base caseif (N 1 || N 2){return N;}return process(N - 1) process(N - 2);}
递归缓存 解题思路 第一先找到重复计算的地方。 第二步把重复计算的放进缓存里记忆化搜索 这个里面的重复计算我们举个例子 f(5) f(4) f(3) f(4) f(3) f(2) 这里面f(3就在重复计算 我们把他加进缓存里 代码演示 /*** 递归加缓存的方式* param N* return*/public static int paLouTi2(int N){if (N 0){return 0;}int[] ans new int[N 1];return process2(N,ans);}/*** 带缓存的递归 记忆化搜索* param N* param ans* return*/public static int process2(int N,int[]ans){//如果有值 直接返回 不在计算if(ans[N] ! 0){return ans[N];}if(N 1 || N 2){ans[N] N;}else{ans[N] process2(N - 1,ans)process2(N - 2,ans);}return ans[N];}
动态规划 动态规划就是在递归加缓存的基础上做的改进我们提前把缓存表计算出来然后直接从缓存表里取值。 代码演示 /*** 动态规划* param N* return*/public static int paLouTi3(int N ){if (N 1){return 0;}//缓存表int[] dp new int[N 1];dp[1] 1;dp[2] 2;for (int i 3; i N;i ){dp[i] dp[i - 1] dp[i - 2];}return dp[N];}
暴力递归到动态规划专题
走到指定位置有多少种方式-从暴力递归到动态规划(java)
零钱兑换,凑零钱问题,从暴力递归到动态规划java
斐波那契数列-从暴力递归到动态规划
