Staircase Traversal

• Time : O(n)
• Space : O(n)

c++

int staircaseTraversal(int h, int s) {
    vector<int> dp(h + 1, 0);
    dp[0] = 1;
    for(int i = 1, sum = 0; i <= h; i++) {
        int st = i - s - 1;
        int ed = i - 1;
        if(st >= 0)
            sum -= dp[st];
        sum += dp[ed];
        dp[i] = sum;
    }
    return dp[h];
}