动态规划--三步问题

?本题题目链接备战技术面试？力扣提供海量技术面试资源，帮助你高效提升编程技能，轻松拿下世界 IT 名企 Dream Offer。https://leetcode.cn/problems/three-steps-problem-lcci/

?个人主页：Lei宝啊?

愿所有美好如期而遇

?

动态规划，如果真要清楚理解的话，可能一开始学习不太可能，专有名词太多，我们就先简单理解。

状态表示，状态转移方程，初始化，填表顺序，返回值，也就分这么几个步骤，也许你不理解，那就对了，我们分开简单说。

状态表示，也就是建一个数组，我们叫做dp表(动态规划缩写)，数组每个值都对应一个状态，本题来说，数组的第一个元素为0，表示没有方法，在原地，第一个元素为1，表示只有一种方法，第二个元素为2，表示我们可以一格格跳以及一次跳两格这两种方法，这就是dp表每个值的状态。我们如何得到他的状态，经验+题目分析(这不是废话嘛)，简单来说，多做题，上百道就差不多有感觉了(滑稽)。

状态转移方程，就是dp[i]等于什么，我们这里写出前几个就能够看出来，0,1,2,4,7,13。

初始化，给初始的几个状态赋值。

填表顺序，就是根据状态转移方程填dp表。

返回值，返回哪个位置的值呢？由你决定。

class Solution {
public:
    int waysToStep(int n) 
    {
        long long result = 0;
        long long a = 1, b = 2, c = 4;

        if(n == 1) return 1;
        if(n == 2) return 2;
        if(n == 3) return 4;

        for(int i=3; i<n; i++)
        {
            result = (a + b + c) % 1000000007;
            a = b;
            b = c;
            c = result;
        }

        return result;

    }
};