斐波那契数列

最简单的递归法：超时
存在大量的重叠子问题，时间复杂度为 $O\left(2^n\right)$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\left[i\right]$f[i] 表示跳上第 $i$i 个台阶的方法数，而第n个台阶可以是由第n-1个台阶跳上的，也可以是由第n-2个台阶跳上的，所以方法数 $f\left[n\right]=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\left[i\right]$f[i] 表示跳上第 $i$i 个台阶的方法数，求 $f\left[n\right]$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) × 4
• n-3 和 3：长度 (n-3) × 3
• n-2 和 2：长度 (n-2) × 2
• n-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;