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

求深入浅出的，实在是蒙了，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.

楼上的解法是动态规划解法
实际上就是算出状态转移方程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把动态规划或者记忆化搜索搞定应该能过应对大部分题目了


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

TonyJang 发表于 2014-10-10 20:26
我想問一下時間複雜度爲什麽是O（N），沒開什麽空間吧

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

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. }
   

复制代码

题目的意思是，让你上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

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

而且他這個上0級臺階的時候，應該返回0啊

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

我想問一下時間複雜度爲什麽是O（N），沒開什麽空間吧

TonyJang 发表于 2014-10-10 20:26
我想問一下時間複雜度爲什麽是O（N），沒開什麽空間吧

前面你说时间复杂度，后面又说空间，不同的东西。

TonyJang 发表于 2014-10-10 20:26
我想問一下時間複雜度爲什麽是O（N），沒開什麽空間吧

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

chopper 发表于 2014-10-10 21:20
前面你说时间复杂度，后面又说空间，不同的东西。

我说的是空间，输入法太操蛋......