C++ 猫跳树问题：动态规划解法

// 一种解决这个问题的方法是使用动态规划。我们可以定义一个数组dp，其中dp[i]表示小猫能否跳到第i棵树上。初始时，dp[1]为true，因为小猫已经在第1棵树上。 // // 然后，我们可以从第2棵树开始遍历到第n棵树，对于每一棵树i，我们需要检查它是否比前面的树都低，并且存在一棵比它低的树j，使得dp[j]为true。如果找到这样的树j，我们将dp[i]设置为true，表示小猫可以跳到第i棵树上。 // // 最后，我们返回dp[n]的值，即小猫能否跳到第n棵树上。 // // 下面是使用C++实现的代码： // cpp
#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)。