c++有n棵树排成一行高度为a1到an其中第1棵树上有一只小猫正准备跳到第2棵树上然后跳到第3棵树上以此类推……但是小猫只能跳到高度比当前树低的树上那么它能否跳到第n棵树上呢?例如5棵树高度分别为5、4、3、2、2则前4棵树都能跳到但是不能从第4棵跳到第5棵。所以答案是no。输入 第一行一个数nn100。第二行n个数依次表示树木高度。输出 能跳到第n棵树上的话输出yes否则输出no。输入样例1 5
一种解决这个问题的方法是使用动态规划。我们可以定义一个数组dp,其中dp[i]表示小猫能否跳到第i棵树上。初始时,dp[1]为true,因为小猫已经在第1棵树上。
然后,我们可以从第2棵树开始遍历到第n棵树,对于每一棵树i,我们需要检查它是否比前面的树都低,并且存在一棵比它低的树j,使得dp[j]为true。如果找到这样的树j,我们将dp[i]设置为true,表示小猫可以跳到第i棵树上。
最后,我们返回dp[n]的值,即小猫能否跳到第n棵树上。
下面是使用C++实现的代码:
#include <iostream>
#include <vector>
using namespace std;
bool canJumpToLastTree(int n, vector<int>& heights) {
vector<bool> dp(n + 1, false);
dp[1] = true;
for (int i = 2; i <= n; i++) {
for (int j = 1; j < i; j++) {
if (heights[j] < heights[i] && dp[j]) {
dp[i] = true;
break;
}
}
}
return dp[n];
}
int main() {
int n;
cin >> n;
vector<int> heights(n + 1);
for (int i = 1; i <= n; i++) {
cin >> heights[i];
}
bool result = canJumpToLastTree(n, heights);
cout << (result ? "yes" : "no") << endl;
return 0;
}
这个解决方案的时间复杂度是O(n^2),空间复杂度是O(n)
原文地址: https://www.cveoy.top/t/topic/ilI3 著作权归作者所有。请勿转载和采集!