20. Ways to Fill Slots with Single or Double Coverage

Origin: Ways to Fill Slots with Single or Double Coverage

Given n slots numbered 0 to n-1, return the number of ways to fill all slots where each operation covers either 1 slot or 2 adjacent slots.

本质上是”爬楼梯”问题：n 阶楼梯，每次走 1 步或 2 步，有多少种走法。

Example 1

Input: n = 3

Output: 3

Explanation: dp[0]=1, dp[1]=1, dp[2]=dp[1]+dp[0]=2, dp[3]=dp[2]+dp[1]=3。序列：[1,1,1], [1,2], [2,1]。

Example 2

Input: n = 5

Output: 8

Explanation: dp[0]=1, dp[1]=1, dp[2]=2, dp[3]=3, dp[4]=5, dp[5]=dp[4]+dp[3]=5+3=8。

Input Format

一个整数 n。

Constraints

• 0 <= n <= 1000

Output Format

输出一个十进制字符串，表示填满 n 个槽位的安装序列数。

注意：n=1000 时结果极大，需要处理大数。

Sample Input 0

2

Sample Output 0

2

Sample Input 1

3

Sample Output 1

3

---

函数契约

// 输入：n（整数，槽位数量）
// 输出：填满所有槽位的方案数（大数，可能需要 BigInt）
// 边界：n=0 → 1（什么都不做）；n=1 → 1（只有 [1]）；n=2 → 2（[1,1] 或 [2]）

边界表

场景	返回什么
n = 0	1
n = 1	1
n = 2	2
n = 1000	极大数，需要 BigInt
正常场景	dp[n]

Resolution

我的解法

function countInstallationSequences(n) {
    let pre = 1n
    let prepre = 1n
    if (n === 0 || n === 1) return '1'
 
    for (let i = 2; i <= n; i++) {
        let tmp = pre
        pre = pre + prepre
        prepre = tmp
    }
    return String(pre)
}

解题思路

本质是爬楼梯：n 个位置排成一排，每次放 1 格或 2 格，放满有多少种方式。

推导过程：

1. 定义状态：dp[i] = 填满 i 个槽位的方案数
2. 最后一步做了什么选择？要么放 1 格（剩 i-1 格，dp[i-1] 种），要么放 2 格（剩 i-2 格，dp[i-2] 种）
3. 转移方程：dp[i] = dp[i-1] + dp[i-2]
4. 边界：dp[0] = 1（什么都不做），dp[1] = 1（只能放 1 格）

和第 19 题的斐波那契一模一样的递推关系，区别只是起始值不同。

踩坑经历

n=1000 时结果极大，和第 19 题一样需要 BigInt。直接用 JavaScript + BigInt，避免 TypeScript 的 number 类型限制。

复杂度

• 时间：O(n)，一次遍历
• 空间：O(1)，两个变量滚动

参考来源

• 相关文章：算法解题流程：从读题到提交的七步
• 相关题目：19. Custom Fibonacci Sequence — 同样是递推关系，同样需要 BigInt 处理大数