10月28,K神开讲数据科学:AB Test/实验设计


一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
天天打游戏、照样领工资、还办H1B
这份工作你要不要?
把贵司招聘信息放这里
查看: 1199|回复: 14
收起左侧

[CareerCup] 求大神解释CC150 9.1爬阶梯递归问题

[复制链接] |试试Instant~ |关注本帖
TonyJang 发表于 2014-10-10 11:40:03 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?Sign Up 注册获取更多干货

x
求深入浅出的,实在是蒙了,A child is running up a staircase with n steps, and can hop either 1 step, 2 steps, or 3 steps at a time. Implement a method to count how many possible ways the child
can run up the stairs.


LiamZhu 发表于 2014-10-10 11:58:27 | 显示全部楼层
题目的意思是,让你上n级的楼梯,每次可以走1,2,3级,3种选择,那么走到n级一共有几种组合
比如n=4的时候有
1,3
1,1,2
2,2
3,1
1,1,1,1
1,2,1
2,1,1

首先令f(n)为上n级楼梯总的方法数
那么呢,上到n级实际可以有3种选择
从n-3到n
从n-2到n
从n-1到n
而且到n-1,n-2,n-3具体几种,就可以通过递归的方法做了
也就是
f(n) = f(n-1)+f(n-2)+f(n-3)
其中
f(1) = 1
f(2) = 2
f(3) = 4

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

miss_snow 发表于 2014-10-10 19:02:24 | 显示全部楼层
楼上的解法是动态规划解法
实际上就是算出状态转移方程dp[n] = dp[n-1] + dp[n-2] + dp[n-3]    和初始条件dp[n] = 1,dp[2] = 2, dp[3] = 4
在不考虑空间复杂度的情况下,动态规划是可以用搜索来做的,而且很多都是深度搜索+记忆化搜索来做
这道题目用递归做法就是如下
1、我们要算dp[n],就要先算dp[n-1],dp[n-2],dp[n-3]   n>3
n如果小于等于3,直接算出结果
dp[n-1],dp[n-2],dp[n-3]分别递归
2、
dp[n-1] 需要递归 dp[n-2] dp[n-3] dp[n-4]
dp[n-2] 需要递归 dp[n-3] dp[n-4] dp[n-5]
dp[n-3] 需要递归 dp[n-4] dp[n-5] dp[n-6]
...
3、递归依次进行, 一直递归到初始状态dp[1] dp[2][ dp[3]
而且既然是深度搜索,那么我们实际上就是先走这么一条路
注意:想象一个树形图,这个树形图有很多种画法,我这里是按照坡度最小的那条边先走,比如第一行是n,第二行左到右依次是n-1 n-2 n-3,第三行从左到右依次是n-2 n-3 n-4 (对应n-1) n-3 n-4 n-5(对应n-2) n-4 n-5 n-6(对应n-3) ...
那么按照dfs做法,最开始走的一条路是
dp[n] -> dp[n-1] -> dp[n-2] -> dp[n-3] -> ... -> dp[6] -> dp[5] -> dp[4] -> dp [3] 递归结束,返回值
dp[n] -> dp[n-1] -> dp[n-2] -> dp[n-3] -> ... -> dp[6] -> dp[5] -> dp[4] -> dp [2] 递归结束,返回值
dp[n] -> dp[n-1] -> dp[n-2] -> dp[n-3] -> ... -> dp[6] -> dp[5] -> dp[4] -> dp [1] 递归结束,返回值
dp[n] -> dp[n-1] -> dp[n-2] -> dp[n-3] -> ... -> dp[6] -> dp[5] -> dp[4] 加上刚才递归结果,返回值
dp[n] -> dp[n-1] -> dp[n-2] -> dp[n-3] -> ... -> dp[6] -> dp[5] -> dp[3] 递归结束,返回值
dp[n] -> dp[n-1] -> dp[n-2] -> dp[n-3] -> ... -> dp[6] -> dp[5] -> dp[2] 递归结束,返回值
dp[n] -> dp[n-1] -> dp[n-2] -> dp[n-3] -> ... -> dp[6] -> dp[5] 加上刚才递归结果,返回值
后面我们会发现进行递归的是这个,因为dp[6]下面对应的一行应该是dp[5] dp[4] dp[3],dp[5]刚刚算完了
dp[n] -> dp[n-1] -> dp[n-2] -> dp[n-3] -> ... -> dp[6] ->  dp[4]这个时候既然我们dp[4]在前面已经算过了,那就只要有一个数组存储一下,然后返回就行
也就是记忆化
记忆化的作用就是把很暴力的时间复杂度压缩
本来这棵树全部暴力来一遍,应该是NP的
但是经过记忆化搜索就是O(n)的,和动态规划的复杂度一样了
不过动态规划可以通过某些方法进行降维操作,目前还没在这几个oj碰到
lz把动态规划或者记忆化搜索搞定应该能过应对大部分题目了


最后!!!码字码的这么辛苦~~~求大米~~~   %>_<%

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

 楼主| TonyJang 发表于 2014-10-10 19:49:34 | 显示全部楼层
LiamZhu 发表于 2014-10-10 11:58
题目的意思是,让你上n级的楼梯,每次可以走1,2,3级,3种选择,那么走到n级一共有几种组合
比如n=4的时 ...

谢谢!你说的好好,可是这个答案代码为啥base case没写f(2),f(3)的情况?
  1. public static int countWaysRecursive(int n) {
  2. if (n < 0) {
  3. return 0;
  4. } else if (n == 0) {
  5. return 1;
  6. } else {
  7. return countWaysRecursive(n - 1) + countWaysRecursive(n - 2) + countWaysRecursive(n - 3);
  8. }
  9. }
复制代码
回复 支持 反对

使用道具 举报

 楼主| TonyJang 发表于 2014-10-10 20:04:11 | 显示全部楼层
LiamZhu 发表于 2014-10-10 11:58
题目的意思是,让你上n级的楼梯,每次可以走1,2,3级,3种选择,那么走到n级一共有几种组合
比如n=4的时 ...

而且他這個上0級臺階的時候,應該返回0啊
回复 支持 反对

使用道具 举报

 楼主| TonyJang 发表于 2014-10-10 20:26:24 | 显示全部楼层
miss_snow 发表于 2014-10-10 19:02
楼上的解法是动态规划解法
实际上就是算出状态转移方程dp[n] = dp[n-1] + dp[n-2] + dp[n-3]    和初始条 ...

我想問一下時間複雜度爲什麽是O(N),沒開什麽空間吧
回复 支持 反对

使用道具 举报

chopper 发表于 2014-10-10 21:20:55 | 显示全部楼层
TonyJang 发表于 2014-10-10 20:26
我想問一下時間複雜度爲什麽是O(N),沒開什麽空間吧

前面你说时间复杂度,后面又说空间,不同的东西。
回复 支持 反对

使用道具 举报

miss_snow 发表于 2014-10-10 22:17:03 | 显示全部楼层
TonyJang 发表于 2014-10-10 20:26
我想問一下時間複雜度爲什麽是O(N),沒開什麽空間吧

额……不好意思,繁体字不太懂……囧
你问的是,为什么时间复杂度是O(N),但没开什么空间?
时间和空间复杂度在这里这么理解吧
就是通过另开一个数组记录当前已经跑过的节点(实际上这个数组可以合并到dp[]数组)
这里就是通过一定量的空间牺牲(另开一个数组;甚至不需要另外再开一个,直接用dp[]就行,这样就毫无牺牲之说)
来换取时间复杂度的大量缩减
回复 支持 反对

使用道具 举报

miss_snow 发表于 2014-10-10 22:17:28 | 显示全部楼层
TonyJang 发表于 2014-10-10 20:26
我想問一下時間複雜度爲什麽是O(N),沒開什麽空間吧

lz是你啊!!!上次那个也是呢!!!给大米的好人O(∩_∩)O哈!

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

 楼主| TonyJang 发表于 2014-10-10 22:21:26 | 显示全部楼层
chopper 发表于 2014-10-10 21:20
前面你说时间复杂度,后面又说空间,不同的东西。

我说的是空间,输入法太操蛋......
回复 支持 反对

使用道具 举报

 楼主| TonyJang 发表于 2014-10-10 22:22:29 | 显示全部楼层
miss_snow 发表于 2014-10-10 22:17
额……不好意思,繁体字不太懂……囧
你问的是,为什么时间复杂度是O(N),但没开什么空间?
时间和空间 ...

你看二楼那位递归的代码,我感觉没开数组啊,怎么空间复杂度是O(N)?时间复杂度我知道
回复 支持 反对

使用道具 举报

miss_snow 发表于 2014-10-10 23:04:57 | 显示全部楼层
TonyJang 发表于 2014-10-10 22:22
你看二楼那位递归的代码,我感觉没开数组啊,怎么空间复杂度是O(N)?时间复杂度我知道

因为他用了动态规划啊
这里动态规划和记忆化搜索的复杂度一样
动态规划写的话就是三个初始值,然后一遍for循环,就是O(N)了

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

miss_snow 发表于 2014-10-10 23:15:37 | 显示全部楼层
lz你是一遍刷G一遍刷题吗???
回复 支持 反对

使用道具 举报

 楼主| TonyJang 发表于 2014-10-10 23:20:27 | 显示全部楼层
miss_snow 发表于 2014-10-10 23:15
lz你是一遍刷G一遍刷题吗???

對啊,我轉專業的,要是找不到工作就去讀個CS的學位
回复 支持 反对

使用道具 举报

miss_snow 发表于 2014-10-10 23:24:51 | 显示全部楼层
TonyJang 发表于 2014-10-10 23:20
對啊,我轉專業的,要是找不到工作就去讀個CS的學位

哦哦,lz加油O(∩_∩)O哈!
回复 支持 反对

使用道具 举报

本版积分规则

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2017-10-21 09:10

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表