#3705. [GESP202406 六级 C++] 第 12 题
[GESP202406 六级 C++] 第 12 题
青蛙每次能跳 1 或 2 步,下面代码计算青蛙跳到第 n 步台阶有多少种不同跳法。则下列说法,错误的是( )。
int jump_recur(int n) {
if (n == 1) return 1;
if (n == 2) return 2;
return jump_recur(n - 1) + jump_recur(n - 2);
}
int jump_dp(int n) {
vector<int> dp(n + 1); // 创建一个动态规划数组,用于保存已计算的值
// 初始化前两个数
dp[1] = 1;
dp[2] = 2;
// 从第三个数开始计算斐波那契数列
for (int i = 3; i <= n; ++i) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
{{ select(1) }}
- 函数
jump_recur()采用递归方式。 - 函数
jump_dp()采用动态规划方法。 - 当
n较大时,函数jump_recur()存在大量重复计算,执行效率低。 - 函数
jump_recur()代码量小,执行效率高。