K12教育赛事综合服务平台
聚乐之家官方网站
下载聚乐之家官方App
专注青少年竞赛题库网站
已知动态规划问题通常包含状态定义、转移方程、初始状态三个核心要素,爬楼梯是典型的入门级动态规划场景。
总方案数为8,dp[i]定义为爬到第i阶的总方案数,转移方程为dp[i] = dp[i-1] + dp[i-2],初始状态dp[1]=1、dp[2]=2
总方案数为5,dp[i]定义为爬i次到达楼顶的方案数,转移方程为dp[i] = dp[i-1] + 2,初始状态dp[1]=1
总方案数为13,该问题用动态规划求解的时间复杂度为O(2^n),空间复杂度必然为O(n)
该问题无法用动态规划求解,只能用递归暴力枚举所有可能的爬楼方案