动态规划算法——三步问题
1.题目解析
2.算法原理
本题可以近似看做泰波那契数列，即小孩到第一个台阶需要一步，到第二个台阶则是到第一个台阶的步数加上第一阶到第二阶的步数，同理第三阶就是第二阶的步数加上第二阶到第三阶的步数，由于小孩只能走三步，所以之后的位置就是该位置前三个位置的步数相加
3.实战代码
class Solution {
public:
int waysToStep(int n)
{
const int MOD = 1e9 + 7;
//处理边界
if(n <= 2)
{
return n;
}
else if(n == 3)
{
return 4;
}
vector<int> 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]) % MOD + dp[i - 3]) % MOD;
}
return dp[n];
}
};