斐波那契数列

最简单的递归法:超时
存在大量的重叠子问题,时间复杂度为 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[n1]+f[n2] ,且初始条件 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) × 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;