网站建设报价明细,ppt做会动彩字网站,美术主题资源网站建设,本地wordpress 手机浏览器本文已收录于专栏#x1f338;《Java入门一百例》#x1f338;学习指引序、专栏前言一、递推与记忆化二、【例题1】1、题目描述2、解题思路3、模板代码4、代码解析5.原题链接三、【例题1】1、题目描述2.解题思路3、模板代码4、代码解析5、原题链接三、推荐专栏四、课后习题序…本文已收录于专栏《Java入门一百例》学习指引序、专栏前言一、递推与记忆化二、【例题1】1、题目描述2、解题思路3、模板代码4、代码解析5.原题链接三、【例题1】1、题目描述2.解题思路3、模板代码4、代码解析5、原题链接三、推荐专栏四、课后习题序、专栏前言 本专栏开启目的在于帮助大家更好的掌握学习Java特别是一些Java学习者难以在网上找到系统地算法学习资料帮助自身入门算法同时对于专栏内的内容有任何疑问都可在文章末尾添加我的微信给你进行一对一的讲解。 但最最主要的还是需要独立思考对于本专栏的所有内容能够进行完全掌握自己完完全全将代码写过一遍对于算法入门肯定是没有问题的。 算法的学习肯定不能缺少总结这里我推荐大家可以到高校算法社区将学过的知识进行打卡以此来进行巩固以及复习。 学好算法的唯一途径那一定是题海战略大量练习的堆积才能练就一身本领。专栏的任何题目我将会从【题目描述】【解题思路】【模板代码】【代码解析】等四板块进行讲解。
一、递推与记忆化 在算法的学习中有许多的题目需要我们递推得到答案这需要我们去发掘出递推式子得到答案。就好比我们在一个有向图上想要到达终点需要从起点一步步找到终点所以相邻的点之间一定会有着某种关联这种关联就是我们的递推式。斐波那契数列和爬楼梯两道题可以说是所有递推入门的经典题目同时递推思想也可以看作是最简单动态规划思想。当然在递推时为了减少重复计算我们还用叫做记忆化的优化方法可以帮我们节省大量的时间。
二、【例题1】
1、题目描述
写一个函数输入 n 求斐波那契Fibonacci数列的第 n 项即 F(N)。斐波那契数列的定义如下
F(0) 0, F(1) 1F(N) F(N - 1) F(N - 2), 其中 N 1.斐波那契数列由 0 和 1 开始之后的斐波那契数就是由之前的两数相加而得出。 答案需要取模 1e971000000007如计算初始结果为1000000008请返回 1。
2、解题思路 核心在于递推式F(N)F(N−1)F(N−2)F(N) F(N - 1) F(N - 2)F(N)F(N−1)F(N−2) 显然式子含义为每个数为前两个数之和我们根据式子递推即可。
3、模板代码
超时代码
class Solution {public int fib(int n) {return f(n);}int f(int x){if(x1) return 1;if(x0) return 0;return (f(x-1)f(x-2))%1000000007;}
}递归记忆化代码
class Solution {int[] anew int[110];public int fib(int n) {Arrays.fill(a,-1);a[0]0;a[1]1;dfs(n);return a[n];}int dfs(int x){if(a[x]!-1) return a[x];return a[x](dfs(x-1)dfs(x-2))%1000000007;}
}递推代码
class Solution {public int fib(int n) {if(n0) return 0;int[] fnew int[n1];f[0]0;f[1]1;for(int i2;in;i){f[i](f[i-1]f[i-2])%1000000007;}return f[n];}
}4、代码解析 显然无论是递推还是记忆化代码我们都需要使用数组记录答案否则当我们求解 f(n)f(n)f(n)时本来我们已经计算出了f(n−1)f(n-1)f(n−1)和f(n−2)f(n-2)f(n−2)结果又得重新计算一次从而导致计算量变大超时。可以直接使用数组递推时其本身就有记忆化功能如果使用递归来进行 dpdpdp则大家最好加上记忆化。
5.原题链接
斐波那契数列
三、【例题1】
1、题目描述
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢
2.解题思路 定义 f(n)f(n)f(n)为走到第 nnn 阶楼梯有多少种走法显然第 nnn 阶只能从第 n−1n-1n−1 或者 n−2n-2n−2 阶走过来于是我们得到递推式 f(n)f(n−1)f(n−2)f(n) f(n - 1) f(n - 2)f(n)f(n−1)f(n−2) (惊喜发现这不是和斐波那契数列一样的吗哈哈哈那么题目迎刃而解啦但是注意初始化有略微区别
3、模板代码
递推代码:
class Solution {public int climbStairs(int n) {int[] fnew int[n1];if(n1) return 1;f[1]1;f[2]2;for(int i3;in;i){f[i]f[i-1]f[i-2];}return f[n];}
}递推记忆化代码
class Solution {int[] fnew int[50];public int climbStairs(int n) {Arrays.fill(f,-1);if(n1) return 1;f[1]1;f[2]2;dfs(n);return f[n];}int dfs(int x){if(f[x]!-1) return f[x];return f[x]dfs(x-1)dfs(x-2);}
}4、代码解析
注意到爬楼梯和斐波那契初始化不同递推式相同。
5、原题链接
爬楼梯
三、推荐专栏
《零基础学算法100天》四、课后习题
序号题目链接难度评级1 使用最小花费爬楼梯1学习有疑问
