三步问题（力扣）n种解法 JAVA

题目：

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

示例1:

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

示例2:

输入：n = 5
输出：13

提示:

n范围在[1, 1000000]之间

解题思路：

记得多次取模防止爆掉int

1、dfs:

class Solution {int INF = 1000000007;public int waysToStep(int n) {return dfs(n) % INF;}public int dfs(int n) {if(n < 0) return 0;if(n == 0) return 1;return ((dfs(n - 1) + dfs(n - 2)) % INF + dfs(n - 3)) % INF;}
}

显然超时，得剪枝

---

2、dfs + 备忘录（剪枝）：

（1）神器 HashMap 备忘录：

class Solution {int INF = 1000000007;Map<Integer, Integer> map = new HashMap<>();public int waysToStep(int n) {map.put(0, 1);return dfs(n) % INF;}public int dfs(int n) {if(n < 0) return 0;if(map.containsKey(n)) return map.get(n);int ans = ((dfs(n - 1)  + dfs(n - 2)) % INF + dfs(n - 3)) % INF;map.put(n, ans);return ans;}
}

当然神器也是有缺陷的即查询需要些许时间，可以试试用数组当备忘录

（2）数组 memo 备忘录：

class Solution {int INF = 1000000007;public static int memo[];public int waysToStep(int n) {memo = new int[n + 1];memo[0] = 1;return dfs(n) % INF;}public int dfs(int n) {if(n < 0) return 0;if(memo[n] != 0) return memo[n];int ans = ((dfs(n - 1) + dfs(n - 2)) % INF + dfs(n - 3)) % INF;memo[n] = ans;return memo[n];}
}

速度快了不少，还有突破空间

---

3、动态规划：

代码:

class Solution {public int waysToStep(int n) {if(n <= 2) return n;if (n == 3) return 4;int[] d = new int[n + 1];d[1] = 1;d[2] = 2;d[3] = 4;for (int i = 4; i <= n; i++){d[i] = (d[i-1] + d[i-2]) % 1000000007 +d[i-3];d[i] %= 1000000007;}return d[n];}
}

不太理解为什么会比 dfs + 剪枝快这么多，这里给出的猜测是递归压栈耗费了大量时间

当然26ms还有突破空间

---

4、利用 static 的储存功能：

之前提到过Java的static修饰变量是有存储功能的不会因为创建新对象就恢复初始化

static简述 JAVA

（1）static 修饰 HashMap:

代码：

class Solution {int INF = 1000000007;public static Map<Integer, Integer> map = new HashMap<>();public int waysToStep(int n) {map.put(0, 1);return dfs(n);}public int dfs(int n) {if(n < 0) return 0;if(map.containsKey(n)) return map.get(n);int ans = ((dfs(n - 1)  + dfs(n - 2)) % INF + dfs(n - 3)) % INF;map.put(n, ans);return ans;}
}

时间大概降了一半

（2）static 修饰 memo 数组：

为了更好储存memo数组要设置最大长度

代码：

class Solution {int INF = 1000000007;public static int memo[] = new int[1000001];public int waysToStep(int n) {memo[0] = 1;return dfs(n) % INF;}public int dfs(int n) {if(n < 0) return 0; if(memo[n] != 0) return memo[n];int ans = ((dfs(n - 1) + dfs(n - 2)) % INF + dfs(n - 3)) % INF;memo[n] = ans;return memo[n];}
}

速度也是之前的一半

---

（3）static 修饰 dp 数组 + 动态规划：

充分利用了动态规划的高效以及static的存储功能设立static变量j避免重复更新数据

代码：

class Solution {public static int dp[] = new int[1000000];public static int j;public int waysToStep(int n) { if(dp[n] != 0) return dp[n];if(n <= 2) return n;if (n == 3) return 4;if(j < 3){dp[0] = 1;dp[1] = 1;dp[2] = 2;dp[3] = 4;j  = 4;} for (int i = j; i <= n; i++) dp[i] = ((dp[i-1] + dp[i-2]) % 1000000007 +dp[i-3]) % 1000000007;j = n;return dp[n];}
}

偶然能触及12ms的边边

---

5、动态规划 + 优化常数空间：

代码：

class Solution {public int waysToStep(int n) {if (n == 1) return 1;if (n == 2) return 2;if (n == 3) return 4;long a = 1, b = 2, c = 4, d;while (--n >= 3) {d = a + b + c;a = b;b = c;c = d % 1000000007;}return (int) c;}
}

这是网上大佬写的也这么快是我没想到的

目前猜测唯一可能是static修饰变量每次创建新对象仍要创建一次数组，且创建数组需要耗费很多时间

---

6、数学 矩阵：

class Solution {public static int  waysToStep(int n) {if (n == 1) {return 1;}if (n == 2) {return 2;}if (n == 3) {return 4;}long[][] m = {{1, 1, 1}, {1, 0, 0}, {0, 1, 0}};long[][] mn = pow(m, n - 3);long res = (mn[0][0] * 4 + mn[0][1] * 2 + mn[0][2] * 1) % 1000000007;return (int) res;}public static long[][] pow(long[][] a, int i) {long[][] val = {{1, 0, 0}, {0, 1, 0}, {0, 0, 1}};while (i != 0) {if ((i % 2) == 1)  {val = multiply(val, a);}a = multiply(a, a);i = i / 2;}return val;}public static long[][] multiply(long[][] a, long[][] b) {long[][] c = new long[3][3];for (int i = 0; i < 3; i++) {for (int j = 0; j < 3; j++) {long s = 0;for (int k = 0; k < 3; k++) {s = (s + (a[i][k] % 1000000007 * b[k][j] % 1000000007)) % 1000000007;}c[i][j] = s % 1000000007;}}return c;}
}

网上大佬写的，真快，给我看傻了