面试题 08.01. 三步问题

题目描述三步问题。有个小孩正在上楼梯楼梯有 n 阶台阶小孩一次可以上 1 阶、2 阶或 3 阶。实现一种方法计算小孩有多少种上楼梯的方式。结果可能很大你需要对结果模 1000000007。示例 1输入n 3输出4说明有四种走法示例 2输入n 5输出13算法原理根据题目所述我们可以进行推导如果要跳上第一级台阶直接从平地起跳1 11步即可方案数为1 11种如果要跳上第二级台阶可以从平地直接跳上去这是1 11种方案也可以从第一级台阶跳上去跳上第一级台阶的方案数为1 11种所以从第一级跳上第二级也是1 11种跳上第二级台阶的方案数总计2 22种如果要跳上第三级台阶可以从平地跳上去这是1 11种方案也可以从第一级台阶跳上去跳上第一级台阶的方案数为1 11种所以从第一级跳上第三级也是1 11种跳上第二级台阶的方案数为2 22种所以从第二级跳上第三级也是2 22种跳上第三级的方案数总计为4 44种根据上面的推导可以确定动态规划的条件创建d p dpdp数组确定状态表示d p [ i ] dp[i]dp[i]指跳上第i ii级台阶的方案数状态转移方程要跳上第i ii级台阶就要先跳上第i − 3 , i − 2 , i − 1 i-3 ,i-2,i-1i−3,i−2,i−1级台阶所以跳上第i ii级台阶的方案数就是跳上第i − 3 , i − 2 , i − 1 i-3 ,i-2,i-1i−3,i−2,i−1级台阶方案数之和也就是d p [ i ] d p [ i − 1 ] d p [ i − 2 ] d p [ i − 3 ] dp[i] dp[i-1] dp[i-2] dp[i-3]dp[i]dp[i−1]dp[i−2]dp[i−3]初始化i 1 , i 2 , i 3 i1, i2,i3i1,i2,i3时i − 3 , i − 2 , i − 1 i-3,i-2,i-1i−3,i−2,i−1会等于负数这时用状态转移方程计算是会越界的所以要先初始化d p [ 1 ] 1 , d p [ 2 ] 2 , d p [ 3 ] 4 dp[1] 1,dp[2] 2,dp[3] 4dp[1]1,dp[2]2,dp[3]4返回值要求的是上第n nn级台阶的方案数所以返回d p [ n ] dp[n]dp[n]代码classSolution{public:intwaysToStep(intn){if(n1)return1;elseif(n2)return2;elseif(n3)return4;vectorintdp(n1,0);intMOD(int)(1e97);dp[1]1,dp[2]2,dp[3]4;for(inti4;in;i){dp[i]((dp[i-1]dp[i-2])%MODdp[i-3])%MOD;}returndp[n];}};