💡 真题解析

【答案】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).