单选题 适中
#21090

青蛙每次能跳1或2步,下面代码计算青蛙跳到第n步台阶有多少种不同跳法。则下列说法,错误的是( )。 int jump_recur ( int n ) { if…

青蛙每次能跳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];
}


未登录也能判分,登录后才会记录
答案与解析
正确答案:D
解析

状态表示:dp[i]表示青蛙到达第i个台阶的跳法。

状态转移方程:第i个台阶由两个状态转移过来①i-2级跳两步②i-1级跳一部,因此状态转移方程为:dp[i]=dp[i-1]+dp[i-2]

目标状态:dp[n]

int jump_recur(int n)使用递归方式(斐波那契),无记忆化,因此复杂度为指数。

int jump_dp(int n)使用动规(递推)方式,复杂度O(n).