第n阶的数量由前两阶的数量相加而来,故用动态规划。
- dp[i]表示第i阶有dp[i]种方法
- 递推公式:dp[i] = dp[i - 1] + dp[i - 2]
- dp数组初始化:dp = [null, 1, 2],dp[0]没有意义,从i=3开始循环
- 遍历顺序:从前往后
为什么不直接初始化dp = [1, 1, 2]
?
dp[0]没有意义,宁可外加条件,也要统一dp数组的含义。
const numWays = n => {
// 为了通过,强行加的条件
if (n === 0) return 1;
const dp = [null, 1, 2];
for (let i = 3; i <= n; i++) {
dp[i] = (dp[i - 1] + dp[i - 2]) % 1000000007;
}
return dp[n];
};