有没有别的解法?
时间: 2024-02-11 17:09:01 浏览: 19
除了动态规划,我们还可以使用递归来解决这个问题。具体而言,对于上 i 级台阶的方案数,我们可以递归计算上 i-1、i-2、i-3 级台阶的方案数,然后将它们相加即可。递归的边界条件是当 i=0 或 1 时,方案数都为1;当 i=2 时,方案数为2。
以下是使用递归的代码实现:
```c
#include <stdio.h>
int climbStairs(int n) {
if (n == 0 || n == 1) {
return 1;
}
if (n == 2) {
return 2;
}
return climbStairs(n-1) + climbStairs(n-2) + climbStairs(n-3);
}
int main() {
int n = 10;
int result = climbStairs(n);
printf("上 %d 级台阶的方案数为 %d\n", n, result);
return 0;
}
```
需要注意的是,递归实现虽然代码简单,但是会重复计算很多子问题,时间复杂度较高,不适合处理大规模数据。
相关问题
有不用vector的解法吗?
是的,你可以使用一个简单的循环来解决这个问题,而不使用`vector`。下面是一个没有使用`vector`的解法示例:
```cpp
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
int maxHours = 0;
int currentHours = 0;
for (int i = 0; i < n; i++) {
int systolic, diastolic;
cin >> systolic >> diastolic;
if (systolic >= 90 && systolic <= 140 && diastolic >= 60 && diastolic <= 90) {
currentHours++;
} else {
maxHours = max(maxHours, currentHours);
currentHours = 0;
}
}
maxHours = max(maxHours, currentHours);
cout << maxHours << endl;
return 0;
}
```
这个解法与前面的解法相似,但是不使用`vector`来存储测量数据。相反,每次读取一对收缩压和舒张压后,直接进行判断和计算。这样可以减少内存的使用,并且不需要额外的数据结构。
输入样例和输出样例与前面相同。你可以将上述代码保存为一个名为`blood_pressure.cpp`的文件,并使用C++编译器进行编译运行。
还有没有其他的解法
除了动态规划和递归,我们还可以使用滚动数组来优化动态规划解法的空间复杂度。具体而言,我们只需要用三个变量表示 dp 数组中的最后三个元素,然后不断更新这三个变量即可。这样可以将空间复杂度优化到 O(1)。
以下是使用滚动数组的代码实现:
```c
#include <stdio.h>
int climbStairs(int n) {
if (n == 0 || n == 1) {
return 1;
}
if (n == 2) {
return 2;
}
int a = 1, b = 1, c = 2;
for (int i = 3; i <= n; i++) {
int d = a + b + c;
a = b;
b = c;
c = d;
}
return c;
}
int main() {
int n = 10;
int result = climbStairs(n);
printf("上 %d 级台阶的方案数为 %d\n", n, result);
return 0;
}
```
需要注意的是,滚动数组虽然优化了空间复杂度,但是也使得代码可读性稍差,需要注意变量的含义。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)