织梦淘宝客网站,深圳市建设网络有限公司网站,设计响应式网站多少钱,北京做erp报价的网站本专栏内容为#xff1a;算法学习专栏#xff0c;分为优选算法专栏#xff0c;贪心算法专栏#xff0c;动态规划专栏以及递归#xff0c;搜索与回溯算法专栏四部分。 通过本专栏的深入学习#xff0c;你可以了解并掌握算法。 #x1f493;博主csdn个人主页#xff1a;小… 本专栏内容为算法学习专栏分为优选算法专栏贪心算法专栏动态规划专栏以及递归搜索与回溯算法专栏四部分。 通过本专栏的深入学习你可以了解并掌握算法。 博主csdn个人主页小小unicorn ⏩专栏分类动态规划专栏 代码仓库小小unicorn的代码仓库 关注我带你学习编程知识 专题一 题目来源题目描述题目解析算法原理1.状态表示2.状态转移方程3.初始化4.填表顺序5.返回值 代码实现 题目来源
本题来源为 Leetcode面试题 08.01. 三步问题 题目描述
三步问题。有个小孩正在上楼梯楼梯有n阶台阶小孩一次可以上1阶、2阶或3阶。实现一种方法计算小孩有多少种上楼梯的方式。结果可能很大你需要对结果模1000000007。
题目解析 我们模拟一下小孩上楼梯的过程会很容易发现规律
算法原理
1.状态表示
经验题目要求
而经验就是以i位置为结尾… 对一维的dp而言基本上就是两种以i位置为结尾…或者以i位置为开始…
…表示根据题目要求进行补充完整。
对于本题而言
dp[i] 表示:到达i位置时,一共有多少种方法
2.状态转移方程
在推导时基本上就是
以i位置的状态最近的一步来划分问题
对于本题而言到达i位置需要分三种情况 因此状态方程为
dp[i]dp[i-3]dp[i-2]dp[i-1];3.初始化
根据状态转移方程本题为防止越界需要处理下标为1,2,3位置的值
dp[1]1;
dp[2]2;
dp[3]4;4.填表顺序
根据状态转移方程我们计算dp[i]位置的值需要i-1与i-2与i-3位置的值因此我们的填表顺序为从左往右
5.返回值
根据题目要求直接返回dp[n]
代码实现
class Solution
{
public:int waysToStep(int n) {// 1.创建dp表// 2.初始化// 3.填表// 4.返回值const int MOD1e97;//处理边界情况if(n1)return 1;if(n2)return 2;if(n3)return 4;//创建dp表vectorint dp(n1);//初始化dp[1]1;dp[2]2;dp[3]4;//填表for(int i4;in;i){dp[i]((dp[i-3]dp[i-2])%MODdp[i-1])%MOD;}return dp[n];}
};
