魔鬼共有n级楼梯要走,魔鬼有他的步伐,每一步他只可以向上走a级楼梯或者b级楼梯,请问走到第n级台阶至少要几步?走不到时输出-1。c++ 记忆化搜索不许用vector
时间: 2024-06-15 11:04:18 浏览: 13
要求走到第n级台阶至少要几步,可以使用动态规划的方法来解决。我们可以定义一个数组dp,其中dp[i]表示走到第i级台阶至少需要的步数。
首先,我们可以初始化dp为0,因为不需要走任何步就已经在第0级台阶上了。
然后,我们可以遍历从1到n的每一级台阶,计算dp[i]的值。对于每一级台阶i,我们有两种选择:向上走a级楼梯或者向上走b级楼梯。因此,我们可以得到状态转移方程:
dp[i] = min(dp[i-a], dp[i-b]) + 1
其中,min表示取两者中的较小值。这个方程的意思是,走到第i级台阶至少需要的步数等于走到第i-a级台阶或者第i-b级台阶至少需要的步数的较小值加上1。
最后,我们可以返回dp[n]作为结果,即走到第n级台阶至少需要的步数。如果dp[n]为无穷大,则表示无法走到第n级台阶,返回-1。
下面是C++的代码实现:
```cpp
#include <iostream>
using namespace std;
int minSteps(int n, int a, int b) {
int dp[n+1];
dp[0] = 0;
for (int i = 1; i <= n; i++) {
dp[i] = INT_MAX;
if (i >= a) {
dp[i] = min(dp[i], dp[i-a] + 1);
}
if (i >= b) {
dp[i] = min(dp[i], dp[i-b] + 1);
}
}
if (dp[n] == INT_MAX) {
return -1;
} else {
return dp[n];
}
}
int main() {
int n, a, b;
cout << "请输入台阶数n:";
cin >> n;
cout << "请输入步伐a和b:";
cin >> a >> b;
int steps = minSteps(n, a, b);
cout << "走到第" << n << "级台阶至少需要" << steps << "步" << endl;
return 0;
}
```
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.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)
![](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)