最简单的递归法：超时 存在大量的重叠子问题，时间复杂度为 O ( 2 n ) O(2^n) O(2n)，很慢，会超时。
class Solution { public: int Fibonacci(int n) { if(n==0 or n==1) return n; return Fibonacci(n-1) + Fibonacci(n-2); } };动态规划： 直接从子树求得答案，过程是从下往上，时间复杂度：O(n)，空间复杂度：O(n)
class Solution { public: int Fibonacci(int n) { if(n==0 or n==1) return n; int a{0}, b{1}, c; for(int i=2; i<=n; i++){ c = a + b; a = b; b = c; } return c; } };题目描述： 一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。
分析： 假设 f [ i ] f[i] f[i] 表示跳上第 i i i 个台阶的方法数，而第n个台阶可以是由第n-1个台阶跳上的，也可以是由第n-2个台阶跳上的，所以方法数 f [ n ] = f [ n − 1 ] + f [ n − 2 ] f[n] = f[n-1] + f[n-2] f[n]=f[n−1]+f[n−2] ，且初始条件 f[1] = 1，f[2] = 2. 本质上还是斐波那契数列。不再附代码了。
题目描述： 一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
分析： 假设 f [ i ] f[i] f[i] 表示跳上第 i i i 个台阶的方法数，求 f [ n ] f[n] f[n] 。
假设现在已经跳到了第 n 个台阶，那么前一步可以从哪些台阶到达呢？
如果上一步跳 1 步到达第 n 个台阶，说明上一步在第 n-1 个台阶，而跳到第n-1个台阶的方法数为f[n-1]；如果上一步跳 2 步到达第 n 个台阶，说明上一步在第 n-2 个台阶，而跳到第n-2个台阶的方法数为f[n-2]；。。。如果上一步跳 n-1 步到达第 n 个台阶，说明上一步在第 1 个台阶。已知跳到 第1个台阶的方法数为f[1] = 1如果上一步跳 n 步到达第 n 个台阶，说明上一步在第 0 个台阶。已知跳到 第0个台阶的方法数为f[0] = 0那么总的方法数就是所有可能的和：f[n] = f[n-1] + f[n-2] + … + f[1] 显然初始条件还是 f[1] =1, f[2] = 2
继续分析：
f[n] = f[n-1] + f[n-2] + … + f[1]， 那么 f[n-1] 呢？ 显然，f[n-1] = ff[n-2] + … + f[1] 原来如此：f[n] = f[n-1] × 2
继续分析：
累乘法: f[n] = f[n-1] × 2 f[n-1] = f[n-2] × 2 … f[3] = f[2] × 2 = 2 × 2 所以：f[n] = pow(2, n-1)
return pow(2, n-1); return 1 << (n-1);题目描述： 长度n大于1，至少剪一下，剪成m段，求m段长度的最大乘积。例如，当绳子的长度是8时，如果剪成长度分别为2、3、3的三段，此时得到的乘积18是最大的。
分析： 求最值问题，考虑递归。自顶向下： 设长度为n的绳子分成m段后的最大乘积为f(n)，则第一次的可能的分法有：
1 和 n-1：长度 1×f(n-1)2 和 n-2：长度 2×f(n-2)···n-4 和 4：长度 (n-4) × 4n-3 和 3：长度 (n-3) × 3n-2 和 2：长度 (n-2) × 2n-1 和 1：长度 (n-1) × 1那么，最大长度是 max{all} 注意：n<4时，不是必须分段则不分的时候是最大的
递归法：超时
class Solution { public: int cutRope(int number) { // 必须分段 if(number < 4) return number-1; return back_track(number); } // 回溯函数，递归 int back_track(int n){ // 不必分段 if (n<=4) return n; int ret = 0; for(int i=1; i<n; i++){ ret = max(ret, i*back_track(n-i)); } return ret; } };辅助空间： 还是自顶向下的思路，只是采用辅助空间，减少重复计算。设定动态数组 m，其中 m[i]表示长度为i的绳子分段后的最大乘积，因此m长度应该为n+1，避免 m[n] 越界。
class Solution { public: int cutRope(int number) { if (number < 4) return number-1; m = vector<int>(number+1, -1); // 添加部分 return back_track(number); } int back_track(int n) { if (n <= 4) return n; if (m[n] != -1) return m[n]; // 添加部分 int ret = 0; for (int i = 1; i < n; ++i) { ret = max(ret, i * back_track(n - i)); } return m[n] = ret; // 添加部分 } private: std::vector<int> m; // 添加部分 };自下而上，迭代求出过程值：
class Solution { public: int cutRope(int number) { if (number < 4) return number-1; std::vector<int> f(number+1, -1); // 自下而上 for(int i=1;i<=4;i++) f[i] = i; for(int i=5; i<=number; i++){ int ret = 0; for(int j=1; j<i; j++){ ret = max(ret, j*f[i-j]); } f[i] = ret; } return f[number]; } };题目描述： 地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于k的格子。 例如，当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。但是，它不能进入方格（35,38），因为3+5+3+8 = 19。请问该机器人能够达到多少个格子？
分析： 求的是机器人接触过的格子树，可以重复经过但不计数。这与我之前论文中的算法很类似：从某点开始，寻找与其接触的并且符合条件的区域，类似于“区域生长”。显然是用递归，找到一点后，再以这一点为起点进行上下左右的搜索。为了避免重复统计，需要一个状态矩阵来记录是否经过了。
C++动态二维数组介绍：https://blog.csdn.net/Augurlee/article/details/107231653 相比Java语法复杂了点。
class Solution { public: int movingCount(int threshold, int _rows, int _cols) { rows = _rows, cols = _cols, T = threshold; state = new int *[rows]; for (int i = 0; i < rows; ++i) state[i] = new int[cols](); walk(0, 0); for (int i = 0; i < rows; ++i) delete[] state[i]; delete[] state; return num; } //void walk(int x, int y) { // 应该把边界检查放在最开始，可以简化代码 // if (not isValid(x, y)) return; // state[x][y] = 1; // num++; // if (x - 1 >= 0 && state[x - 1][y] != 1) walk(x - 1, y); // 上 // if (x + 1 < rows && state[x + 1][y] != 1) walk(x + 1, y); // 下 // if (y - 1 >= 0 && state[x][y - 1] != 1) walk(x, y - 1); // 左 // if (y + 1 < cols && state[x][y + 1] != 1) walk(x, y + 1); // 右 //} void walk(int x, int y) { if (x < 0 || x >= rows || y<0 || y>=cols) return; // 边界检查 if (not isValid(x, y) || state[x][y] == 1) return; // 规则检查 state[x][y] = 1; num++; walk(x - 1, y); // 上 walk(x + 1, y); // 下 walk(x, y - 1); // 左 walk(x, y + 1); // 右 } bool isValid(int x, int y) { int sum = 0; while (x) { sum += x % 10; x = x / 10; } while (y) { sum += y % 10; y = y / 10; } return sum <= T; } private: int rows = 0, cols = 0, T = 0, num= 0; int **state = nullptr; };也可以用vector实现，效果都一样。
题目描述： 判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。 暗含条件：必须是连续地经过相同字符的格子。
分析： 与上一题一样，递归：找到一点后，再以这一点为起点进行上下左右的搜索，注意边界检查和规则检查。
上一题介绍过了，应该把边界检查放在最开始，可以简化代码。如下：
class Solution { public: bool hasPath(char* matrix, int rows, int cols, char* str) { this->rows = rows; this->cols = cols; this->mat = matrix; // 从每个点开始找路径 for (int i = 0; i < rows * cols; ++i) { int* state = new int[rows * cols](); // 状态矩阵，记录是否经过了 if (dfs(i / cols, i % cols, str, 0, state)) return true; delete[] state; } return false; } bool dfs(int x, int y, char* str, int index, int* state) { if (str[index] == '\0') return true; if (x < 0 || x >= rows || y<0 || y>cols) return false; // 边界检查 if (mat[cols * x + y] != str[index] || state[cols * x + y] == 1) return false; // 规则检查 // 记录经过的格子 state[cols * x + y] = 1; // 在相邻格子中寻找下一个字符 index++; if (dfs(x, y - 1, str, index, state) || // 左 dfs(x, y + 1, str, index, state) || // 右 dfs(x - 1, y, str, index, state) || // 上 dfs(x + 1, y, str, index, state)) // 下 return true; else return false; } private: char* mat; int rows, cols; };题目要求： 求1+2+3+…+n，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）
分析： 考虑递归，但需要判断回溯条件，如：
int Sum_Solution(int n){ if(n==1) return 1; return n+Sum_Solution(n-1); }改变语法：(扩展视野吧，没啥优势)
int Sum_Solution(int n) { bool flag = n>1 && (n+=Sum_Solution(n-1)); return n; }有网友提出还可以这样…
return static_cast<int>(pow(n,2) + n) >> 1;