爬楼梯「变题」

70. 爬楼梯

// 时间复杂度 : O(n)
// 空间复杂度 : O(n)
public int climbStairs(int n) {
    if (n <= 2) return n;
    int[] f = new int[n + 1];
    f[1] = 1; f[2] = 2;
    for (int i = 3; i <= n; i++) {
        f[i] = f[i - 1] + f[i - 2];
    }
    return f[n];
}

变题一：空间优化

// 时间复杂度 : O(n)
// 空间复杂度 : O(1)
public int climbStairs(int n) {
    if (n <= 2) return n;
    int f1 = 1, f2 = 2, f = 0;
    for (int i = 3; i <= n; i++) {
        f = f1 + f2;
        f1 = f2;
        f2 = f;
    }
    return f;
}

变题二：扩展至 m 阶数

相似题目可见 DP3 跳台阶扩展问题

public int climbStairs(int n) {
    int[] f = new int[n + 1];
    f[0] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; i - j >= 0 && j <= m; j++) {
            f[i] += f[i - j];
        }
    }
    return f[n];
}

变题三：输出所有跳法

private int n;
private List<Integer> track = new ArrayList<>();
private List<List<Integer>> path = new ArrayList<>();
public int climbStairs(int n) {
    this.n = n;
    int ans = f(0);
    System.out.println(path);
    return ans;
}
private int f(int i) {
    if (i > n) return 0;
    if (i == n) {
        path.add(new ArrayList<>(track));
        return 1;
    }
    track.add(1);
    int t1 = f(i + 1);
    track.remove(track.size() - 1);
    
    track.add(2);
    int t2 = f(i + 2);
    track.remove(track.size() - 1);
    return t1 + t2;
}

变题四：不能爬到 7 及 7 的倍数

public int climbStairs(int n) {
    if (n <= 2) return n;
    int[] f = new int[n + 1];
    f[1] = 1; f[2] = 2;
    for (int i = 3; i <= n; i++) {
        // 若为 7 的倍数，直接为 0
        if (i % 7 == 0) f[i] = 0;
        else f[i] = f[i - 1] + f[i - 2];
    }
    return f[n];
}