K12教育赛事综合服务平台
聚乐之家官方网站
下载聚乐之家官方App
专注青少年竞赛题库网站
爬楼梯问题描述：每次可以选择爬1个或2个台阶，求从第0个台阶（起点）爬到第n个台阶（n为正整数）的不同走法总数量。
可定义状态dp[i]为爬到第i个台阶的不同走法数，递推公式为dp[i] = dp[i-1] + dp[i-2]，初始边界设置为dp[0] = 1、dp[1] = 1
dp[i]
dp[i] = dp[i-1] + dp[i-2]
dp[0] = 1
dp[1] = 1
可定义状态dp[i]为爬到第i个台阶的不同走法数，递推公式为dp[i] = dp[i-1] + 2 * dp[i-2]，初始边界设置为dp[0] = 1、dp[1] = 1
dp[i] = dp[i-1] + 2 * dp[i-2]
可定义状态dp[i]为爬到第i个台阶的不同走法数，递推公式为dp[i] = dp[i-1] + dp[i-2]，初始边界设置为dp[0] = 0、dp[1] = 2
dp[0] = 0
dp[1] = 2
该问题存在大量重叠子问题，无法使用动态规划求解，只能通过回溯算法暴力枚举所有走法统计数量