用什么做网站后台的,顺义企业网站建站公司,合肥论坛网站制作,广告狂人dp经典问题#xff1a;爬楼梯 爬楼梯
三步问题。有个小孩正在上楼梯#xff0c;楼梯有n阶台阶#xff0c;小孩一次可以上1阶、2阶或3阶。实现一种方法#xff0c;计算小孩有多少种上楼梯的方式。结果可能很大#xff0c;你需要对结果模1000000007。
Step1: 识别问题
这…dp经典问题爬楼梯 爬楼梯
三步问题。有个小孩正在上楼梯楼梯有n阶台阶小孩一次可以上1阶、2阶或3阶。实现一种方法计算小孩有多少种上楼梯的方式。结果可能很大你需要对结果模1000000007。
Step1: 识别问题
这个问题要求我们计算 小孩上到第n阶台阶有多少种方法
Step2定义状态 d p [ i ] − 小孩上到第 n 阶台阶的方法数量定义为第 i 个状态 dp[i] - 小孩上到第n阶台阶的方法数量定义为 第 i 个状态 dp[i]−小孩上到第n阶台阶的方法数量定义为第i个状态
Step3确定状态转移方程
这里 小孩每次可以上1阶2阶或3阶 ,也就是说小孩可以从前1阶2阶或者3阶上到当前台阶
也就是说当前状态由前三个状态决定 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]
Step4确定初始状态和边界 d p [ 0 ] 1 d p [ 1 ] 1 d p [ 2 ] 2 d p [ 3 ] 4 dp[0]1\\ dp[1]1\\ dp[2]2\\ dp[3]4 dp[0]1dp[1]1dp[2]2dp[3]4
Step5计算目标状态值
只需要从第四个状态开始自下而上的状态推导即可
代码
class Solution {
public:int waysToStep(int n) {if (n 1) return 1;if (n 2) return 2;if (n 3) return 4;vectorint dp(n 1);dp[0] 1;dp[1] 1;dp[2] 2;dp[3] 4;const int mod 1000000007;for (int i 4; i n; i) {dp[i] ((dp[i - 1] dp[i - 2]) % mod dp[i - 3]) % mod;}return dp[n];}
};
