面试题 08.01 三步问题

链接：https://leetcode-cn.com/problems/three-steps-problem-lcci/

三步问题。有个小孩正在上楼梯，楼梯有n阶台阶，小孩一次可以上1阶、2阶或3阶。实现一种方法，计算小孩有多少种上楼梯的方式。结果可能很大，你需要对结果模1000000007。

输入：n = 3 
输出：4
说明: 有四种走法输入：n = 5
输出：13

解法1：动态规划

这道题与之前的青蛙上楼梯的问题基本是相同的，无非是多了一种i - 3的情况，我出的问题在于取模操作，之前没有注意，由于结果很大，需要对每一项以及计算后的结果进行取模

var waysToStep = function (n) {let dp = [1, 2, 4];for (let i = 3; i < n; i++) {dp[i] = (((dp[i - 1] + dp[i - 2]) % 1000000007) + dp[i - 3]) % 1000000007;}return dp[n - 1];
};

执行结果：执行用时132ms，打败了51%的JavaScript提交，内存消耗: 69.8MB ，打败了38%的JavaScript提交

解法2：动态规划优化

同样是上面的思路，但是实际上我们不需要保存整个数组，只需要保存3个变量，不断迭代更新即可

var waysToStep = function (n) {if (n === 1) {return 1;}if (n === 2) {return 2;}if (n === 3) {return 4;}let dp1 = 1,dp2 = 2,dp3 = 4;for (let i = 3; i < n; i++) {const temp = (((dp3 + dp2) % 1000000007) + dp1) % 1000000007;dp1 = dp2;dp2 = dp3;dp3 = temp;}return dp3;
};

执行结果：执行用时92ms，打败了96%的JavaScript提交，内存消耗: 37.9MB ，打败了94%的JavaScript提交