算法日常・每日刷题--＜动态规划＞2

面试题 08.01. 三步问题 - 力扣LeetCode面试题 08.01. 三步问题 - 三步问题。有个小孩正在上楼梯楼梯有 n 阶台阶小孩一次可以上 1 阶、2 阶或 3 阶。实现一种方法计算小孩有多少种上楼梯的方式。结果可能很大你需要对结果模 1000000007。示例 1 输入n 3 输出4 说明有四种走法示例 2 输入n 5 输出13提示: 1. n 范围在[1, 1000000]之间https://leetcode.cn/problems/three-steps-problem-lcci/题目面试题 08.01. 三步问题三步问题。有个小孩正在上楼梯楼梯有n阶台阶小孩一次可以上 1 阶、2 阶或 3 阶。实现一种方法计算小孩有多少种上楼梯的方式。结果对1e97取模。DP 五部曲dp 数组含义dp[i]到达第i阶台阶一共有多少种走法状态转移方程dp[i] dp[i‑1] dp[i‑2] dp[i‑3]到 i 阶可以从 i‑1 走 1 步i‑2 走 2 步i‑3 走 3 步三种情况相加。初始化dp[1]1dp[2]2dp[3]4遍历顺序i 从 4 到 n从小到大正向遍历返回dp[n]class Solution { public: const int MOD 1000000007; int waysToStep(int n) { if(n 1) return 1; if(n 2) return 2; if(n 3) return 4; vectorlong long dp(n 1); dp[1] 1; dp[2] 2; dp[3] 4; for(int i 4; i n; i) { dp[i] (dp[i-1] dp[i-2] dp[i-3]) % MOD; } return (int)dp[n]; } };