#牛客堂直播视频#斐波那契数列(2015.7.22)

【本期题目】 
1、斐波那契系列问题的递归和动态规划
【题目】
给定整数N,返回斐波那契数列的第N项。
【补充题目1】
给定整数N,代表台阶数,一次可以跨2个或者1个台阶,返回有多少种走法。
【举例】
N=3。可以三次都跨1个台阶;也可以先跨2个台阶,再跨1个台阶;还可以先跨1个台阶,再跨2个台阶。所以有三种走法,返回3。
【补充题目2】
假设农场中成熟的母牛每年只会生1头小母牛,并且永远不会死。第一年农场有1只成熟的母牛,从第二年开始,母牛将开始生小母牛。每只小母牛3年之后成熟又可以开始生小母牛。给定整数N,求出N年后牛的数量。
【举例】
N=6。第1年1头成***牛记为a。第2年a生了新的小母牛记为b,总牛数为2。第3年a生了新的小母牛记为c,总牛数为3。第4年a生了新的小母牛记为d,总牛数为4。第5年b成熟了,a和b分别生了新的小母牛,总牛数为6。第6年c也成熟了,a、b和c分别生了新的小母牛,总牛数为9。返回9。

2、换钱的方法数
【题目】
给定数组arr,arr中所有的值都为正数且不重复。每个值代表一种面值的货币,每种面值的货币可以使用任意张,再给定一个整数aim代表要找的钱数,求换钱有多少种方法。
【举例】
arr=[5,10,25,1],aim=0。
组成0元的方法有1种,就是所有面值的货币都不用。所以返回1。
arr=[5,10,25,1],aim=15。
组成15元的方法有6种,分别为3张5元,1张10元+1张5元,1张10元+5张1元,10张1元+1张5元,2张5元+5张1元,15张1元。所以返回6。
arr=[3,5],aim=2。
任何方法都无法组成2元。所以返回0。

注:下面回帖给出了源代码供参考。

【分享嘉宾介绍】
左程云
华中科技大学本科--计算机科学与技术专业、 芝加哥大学硕士--计算机科学专业
IBM软件工程师、 百度软件工程师、 刷题5年的算法热爱者
《程序员代码面试指南--IT名企算法与数据结构题目最优解》 作者,电子工业出版社7月底将出版发行,书籍涉及算法与数据结构编程题目240道以上,并且个人实现出最优解,大部分题目为面试高频题

【参与牛客堂直播】
每周三晚8:00~9:30,直播页面http://www.nowcoder.com/live/courses

【直播题目讨论】
加入牛客5群272820159
全部评论
本期答案领取地址:  加入牛客讨论2群(244930442 ) 群资料中文件:2015-07-22正式版.pdf
点赞 回复 分享
发布于 2015-07-23 17:39
讲的很好。收获很大
点赞 回复 分享
发布于 2017-08-11 17:45
现在还能看吗?
点赞 回复 分享
发布于 2017-04-08 12:25
受教,学习了
点赞 回复 分享
发布于 2016-09-27 20:39
不错
点赞 回复 分享
发布于 2016-08-07 16:16
程云大师真牛,
点赞 回复 分享
发布于 2015-12-10 08:26
xiexie
点赞 回复 分享
发布于 2015-11-29 19:55
非常好
点赞 回复 分享
发布于 2015-10-16 21:25
good
点赞 回复 分享
发布于 2015-10-09 13:43
左神,求答案~
点赞 回复 分享
发布于 2015-09-30 09:20
是不是递推式一样,系数矩阵中的数就确定了,跟具体每一项的数值无关a
点赞 回复 分享
发布于 2015-09-23 00:06
讲的很清楚啊
点赞 回复 分享
发布于 2015-09-20 14:54
public class SplitMoney { int[][] table = new int[5][3001]; public static void main(String[] args) { int[] arr = new int[]{5,10,25,1}; int aim = 3000; SplitMoney splitMoney = new SplitMoney(); long time1= System.currentTimeMillis(); System.out.println(splitMoney.splitSearchTable(arr,0,aim)); long time2= System.currentTimeMillis(); System.out.println("search table method time (ms):"+(time2-time1)); time1= System.currentTimeMillis(); System.out.println(splitMoney.splitRecursive(arr, 0, aim)); time2= System.currentTimeMillis(); System.out.println("recursive method time (ms):"+(time2-time1)); } public int splitRecursive(int[] arr,int start,int aim){ if(arr==null|| arr.length==0 || aim<=0){ return 0; } return splitProcess(arr,start,aim); } public int splitProcess(int[] arr,int start,int aim){ int sum =0; if(aim==0){ return 1; } if(start==arr.length){ return 0; } else{ while(aim>=0){ sum+=splitProcess(arr, start + 1, aim); aim = aim-arr[start]; } } return sum; } public int splitSearchTable(int[] arr,int start,int aim){ if(arr==null|| arr.length==0 || aim<=0){ return 0; } return splitProcess1(arr, start, aim); } public int splitProcess1(int[] arr,int start,int aim){ int sum =0; if(aim==0){ table[start][aim]=1; return 1; } if(start==arr.length){ return 0; } else{ while(aim>=0){ if(table[start][aim]!=0){ sum += table[start][aim]; } else { sum += splitProcess1(arr, start + 1, aim); } aim -=arr[start]; } } if(aim>=0){ table[start][aim] = sum; } return sum; } } 分钱的那道题: 为什么我的程序跑出来的结果是: 3681531 search table method time (ms):13912 3681531 recursive method time (ms):3049 按照常理来讲应该记忆化搜索比暴力递归的时间要短啊。谁能帮我看一看这个是为什么?
点赞 回复 分享
发布于 2015-09-18 15:51
nice啊
点赞 回复 分享
发布于 2015-09-15 10:42
那个矩阵乘法,有点像线性代数里面的题目,用正交化
点赞 回复 分享
发布于 2015-09-13 17:58
在其他地方没有学到过这些
点赞 回复 分享
发布于 2015-09-11 20:18
老师讲的真好  
点赞 回复 分享
发布于 2015-09-10 16:32
为什么看不了?
点赞 回复 分享
发布于 2015-09-04 20:09
回帖可以看?
点赞 回复 分享
发布于 2015-09-03 19:23
讲得很好,涨姿势了
点赞 回复 分享
发布于 2015-09-03 16:30

相关推荐

点赞 评论 收藏
分享
屌丝逆袭咸鱼计划:心态摆好,man,晚点找早点找到最后都是为了提升自己好进正职,努力提升自己才是最关键的😤难道说现在找不到找的太晚了就炸了可以鸡鸡了吗😤早实习晚实习不都是为了以后多积累,大四学长有的秋招进的也不妨碍有的春招进,人生就这样
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务