70. Climbing Stairs (Advanced Version)

KamCoder: 57. Climbing Stairs (opens new window)

Suppose you are climbing stairs. It takes n steps to reach the top.

Each time you can climb at most m (1 <= m < n) steps. How many different ways can you climb to the top?

Note: n is a positive integer.

Input Description: The input consists of a single line containing two positive integers, representing n and m.

Output Description: Output an integer, representing the number of ways to climb to the top.

Sample Input: 3 2

Sample Output: 3

Hints:

When m = 2, n = 3, n = 3 means there are three steps in total, m = 2 means you can climb one step or two steps each time.

In this case, there are three ways to climb to the top.

• 1 step + 1 step + 1 step
• 1 step + 2 steps
• 2 steps + 1 step

Approach

When we previously discussed this problem, as the knapsack problem had not been introduced yet, we only covered the most direct dynamic programming method for climbing stairs (Fibonacci).

Now that we've tackled the knapsack problem, let's climb stairs with our viewers once again!

In the previous problem, we could only climb at most two steps.

This time, it's modified to: climb one step, two steps, three steps, ..., up to m steps at one time. How many different ways can you climb to the top?

This raises the difficulty level, transforming this into a complete knapsack problem.

1 step, 2 steps, ..., up to m steps are items, and the top of the stairs is the knapsack.

Each step can be used repeatedly, for example, take 1 step and then take another 1 step.

Asking how many ways there are to reach the top is essentially asking how many ways there are to fill the knapsack.

By now, you should realize that this is indeed a complete knapsack problem!

It's almost identical to yesterday’s problem 377. Combination Sum IV (opens new window).

Dynamic programming analysis follows:

1. Define the dp array and the meaning of its index

dp[i]: There are dp[i] ways to climb to the top with i steps.

2. Define the recurrence relation

As we discussed in 494. Target Sum (opens new window), 518. Coin Change II (opens new window), and 377. Combination Sum IV (opens new window), when seeking the number of ways to fill a knapsack, the recurrence relation typically takes the form of dp[i] += dp[i - nums[j]];

In this problem, dp[i] has several sources: dp[i - 1], dp[i - 2], dp[i - 3], etc., i.e., dp[i - j].

So the recurrence relation is: dp[i] += dp[i - j]

3. How to initialize the dp array

Since the recurrence relation is dp[i] += dp[i - j], dp[0] must be 1. It is the foundation of all other values in the recurrence. If dp[0] is 0, all other values will be 0 as well.

Non-zero indices in the dp array should be initialized to 0 because dp[i] is accumulated from dp[i-j], and it should not affect the result if it is inherently 0.

4. Determine the traversal order

This is a permutation problem in the knapsack problem—steps 1, 2 (1 step + 2 steps or 2 steps + 1 step) are different ways to cover three steps!

Place target in the outer loop and nums in the inner loop.

Each step can be taken multiple times; this is a complete knapsack, so the inner loop should iterate from front to back.

5. Example to deduce the dp array

Given that this problem is almost identical to 377. Combination Sum IV (opens new window), I won’t provide another example here.

The above completes our analysis. Here's the C++ code:

#include <iostream>
#include <vector>
using namespace std;
int main() {
    int n, m;
    while (cin >> n >> m) {
        vector<int> dp(n + 1, 0);
        dp[0] = 1;
        for (int i = 1; i <= n; i++) { // Traverse the knapsack
            for (int j = 1; j <= m; j++) { // Traverse the items
                if (i - j >= 0) dp[i] += dp[i - j];
            }
        }
        cout << dp[n] << endl;
    }
}

• Time complexity: O(n * m)
• Space complexity: O(n)

In the code, m represents the maximum number of steps you can climb, changing m to 2 gives the same solution as the LeetCode problem "70. Climbing Stairs".

Note that LeetCode uses the core code mode while KamCoder uses the ACM mode.

Summary

This problem appears simple, but a slight enhancement turns it into a complete knapsack problem!

If I were conducting an interview, I would initially present candidates with the original problem, observing their performance. If they successfully solve it, I would then challenge them with the task of figuring out how to accommodate [1 - m] steps each time.

This further allows testing the logic of nested for loops, why target is on the outside, and nums on the inside.

This comprehensive process effectively assesses one's grasp of the knapsack problem's core principles, determining whether the candidate simply memorizes formulas or truly understands them.

This problem's brief code and ordinary premise, when coupled with a nuanced elevation, can fully evaluate knowledge of the complete knapsack problem. Furthermore, it's absent from LeetCode in its advanced form, which helps in eliminating those just rehearsing problems. It's a perfect choice for interview scenarios!

Other Language Versions

Java:

import java.util.Scanner;
class climbStairs {
    public static void main(String [] args) {
        Scanner sc = new Scanner(System.in);
        int m, n;
        while (sc.hasNextInt()) {
            // Input parameters from keyboard, separated by space
            n = sc.nextInt();
            m = sc.nextInt();

            // Seeking permutation problems, first traverse knapsack then traverse items
            int[] dp = new int[n + 1];
            dp[0] = 1;
            for (int j = 1; j <= n; j++) {
                for (int i = 1; i <= m; i++) {
                    if (j - i >= 0) dp[j] += dp[j - i];
                }
            }
            System.out.println(dp[n]);
        }
    }
}

Python3:

def climbing_stairs(n,m):
    dp = [0]*(n+1) # Total capacity of the knapsack
    dp[0] = 1 
    # Permutation problem, mind the loop order, knapsack outside, items inside
    for j in range(1,n+1):
        for i in range(1,m+1):
            if j>=i:
                dp[j] += dp[j-i] # Here i is the weight, not the index
    return dp[n]

if __name__ == '__main__':
    n,m = list(map(int,input().split(' ')))
    print(climbing_stairs(n,m))

Go:

package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
	"strings"
)

func climbStairs(n int, m int) int {
    dp := make([]int, n+1)
    dp[0] = 1   
    for i := 1; i <= n; i++ {
        for j := 1; j <= m; j++ {
            if i-j >= 0 {
                dp[i] += dp[i-j]
            }
        }
    }   
    return dp[n]
}

func main() {
    // Read input `n, m`
    reader := bufio.NewReader(os.Stdin)
    input, _ := reader.ReadString('\n')
    input = strings.TrimSpace(input)
    nv := strings.Split(input, " ")
    n, _ := strconv.Atoi(nv[0])
    m, _ := strconv.Atoi(nv[1]) 
    result := climbStairs(n, m)
    fmt.Println(result)
}

JavaScript:

var climbStairs = function (n) {
  let dp = new Array(n + 1).fill(0);
  dp[0] = 1;
  // Permutation problem, mind the loop order, knapsack outside, items inside
   for (let j = 1; j <= n; j++) {// Traverse knapsack
    for (let i = 1; i <= 2; i++) {// Traverse items
     if (j - i >= 0) dp[j] = dp[j] + dp[j - i];
    }
  }
  return dp[n];
}

TypeScript:

var climbStairs = function (n: number): number {
    let dp: number[] = new Array(n + 1).fill(0);
    dp[0] = 1;
    for (let j = 1; j <= n; j++) {// Traverse knapsack
        for (let i = 1; i <= 2; i++) {// Traverse items
            if (j - i >= 0) dp[j] = dp[j] + dp[j - i];
        }
    }
    return dp[n];
}

Rust: