递归中的 DFS 与 DP 比较
一,递归
递归的过程我们可以认为是:一棵树的根节点向下搜索,并回溯的过程。 我们把根节点连接到所有通过递归延伸到的节点,该树即为递归树。
分支节点下面的第一条路径是通过调用递归函数延伸的,而该分支节点下的其它路径则是通过回溯延伸的。
二,超级楼梯的两种解法
1,题目
有一超级楼梯,共无限级。刚开始时你在地面,你可以一步跨上第一级,也可以一步跨上第二级。 假设你每次只能向上跨一级或二级,那么你要走上第N级,共有多少种走法?
2,DP 解法
将该问题分解为与前面几种状态的小问题,即到达第n个台阶的前一步,要么是从第n-1个台阶走上来的,要么是从n-2台阶走上来的,所以到达第n个台阶的走法就等于到达第n-1个台阶的走法加上到达第n-2个台阶的走法。则有:
递归函数:f(n) = f(n-1) + f(n-2)
函数出口:n == 1 的时候,f(n) = 1;n == 2 的时候,f(n) = 2
#define _CRT_SECURE_NO_WARNINGS #include<stdio.h> #include<stdlib.h> #define N 50 int dp(int n) { if (n == 1) return 1; if (n == 2) return 2; return dp(n - 1) + dp(n - 2); } int main(void) { int n; while (scanf("%d", &n) != EOF) { printf("%d ", dp(n)); } return 0; }
3,DFS 解法
这一题问的是有多少走法,那么我们除了用 dp 的方法,也可以利用 DFS 遍历每一种走法,然后用形参记录递归树的叶节点个数。
注意点:如果要保证某节点能够分支,那么该节点调用递归函数时,不能使用 return,因为 return 的话,直接返回上一层了,相当于截断该分支节点的所有分支。
#define _CRT_SECURE_NO_WARNINGS #include<stdio.h> #include<stdlib.h> #define N 50 int dfs(int n, int &cnt) { if (n > 1) dfs(n - 2, cnt); if (n > 0) dfs(n - 1, cnt); if (n == 0) cnt = cnt + 1; return cnt; } int main(void) { int n; while (scanf("%d", &n) != EOF) { int cnt = 0; printf("%d ", dfs(n, cnt)); } return 0; }