前言
接着上篇博客详解递归思想我们继续更深入地分析递归,本篇主要更加深入讲解上篇的自下而上和自上而下思想.
啥叫「自顶向下」？是从上向下延伸，都是从一个规模较大的原问题比如说 f(20)，向下逐渐分解规模，直到 f(1) 和 f(2) 这两个base case，然后逐层返回答案，这就叫「自顶向下」。
啥叫「自底向上」？反过来，我们直接从最底下、最简单、问题规模最小、已知结果的 f(1) 和 f(2)（base case）开始往上推，直到推到我们想要的答案 f(20)。这就是「递推」的思路，这也是动态规划一般都脱离了递归，而是由循环迭代完成计算的原因。
上楼梯
思路:
自上而下:递归,你会发现这个代码看起来很简单，不过很难理解,因为它是顺着想倒着写、
#define mod 1000000007; typedef long long ll; ll recursion(int n) { if (n < 0)return 0; if (n == 0 || n == 1)return 1; if (n == 2)return 2; return recursion(n - 1) % mod + recursion(n - 2) % mod + recursion(n - 3) % mod; }
自下而上:迭代,这个很好理解,它是顺着想顺着写 ，就是定义x1,x2,x3三个变量来记录各个台阶需要走的步数，并且及时更新;
#include<iostream> using namespace std; #define mod 1000000007; typedef long long ll; ll recursion(int n) { if (n < 0)return 0; if (n == 0 || n == 1)return 1; if (n == 2)return 2; if (n == 3) return 4; int x1 = 1; int x2 = 2; int x3 = 4; for (int i = 4; i <= n; i++) { int x_1 = x1; x1 = x2 % mod; x2 = x3 % mod; x3 = ((x1 + x2)% mod + x_1)% mod; } return x3; }
例题练习:爬楼梯
机器人走方格
思路:
自上而下:递归
int solvw(int x, int y) { if (x == 1 || y == 1)return 1;//边界即推理的起点 return solvw(x - 1, y) + solvw(x, y - 1); }
自下而上:迭代 ；你会发现行数或者列数有一个为1时,不管你另一个取多少,都只有一种走法,边界即推理的起点;由二个分量来决定一个值的时候他就是个二维表结构。
代码:
public static int solve(int m, int n) { int[][] state = new int[m + 1][n + 1]; for (int i = 1; i <= n; i++) { state[1][i] = 1; } for (int j = 1; j <= m; j++) { state[j][1] = 1; } for (int i = 2; i <= m; i++) { for (int j = 2; j <= n; j++) { state[i][j] = state[i][j - 1] + state[i - 1][j]; } } return state[m][n]; }
