C++刷题笔记：动态规划和递归
斐波那契数列
最简单的递归法：超时
存在大量的重叠子问题，时间复杂度为 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] 表示跳上第 i 个台阶的方法数，而第n个台阶可以是由第n-1个台阶跳上的，也可以是由第n-2个台阶跳上的，所以方法数 f[n]=f[n−1]+f[n−2] ，且初始条件 f[1] = 1，f[2] = 2. 本质上还是斐波那契数列。不再附代码了。
变态跳台阶
题目描述：
一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
分析：
假设 f[i] 表示跳上第 i 个台阶的方法数，求 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;
