Dynamic Programming (An Intro)

Looking at the Wikipedia definition of dynamic programming (DP in short) we can see it is

...it refers to simplifying a complicated problem by breaking it down into simpler sub-problems in a recursive manner...

and that's exactly what it is (you will find bunch of other stuff in the article, but let's keep it simple for now).
Let's look at an example problem that may help you understand it better - the famous Ladder Problem.

Problem Statement

You are standing at the bottom of a ladder with n rungs. You can climb the ladder by taking 1 step, 2 steps, ..., up to k steps at a time. Count the number of distinct ways you can reach the top of the ladder (i.e., the nth rung).

In this post I will explore a simpler version of the problem and generalize to the one above later:

You are standing at the bottom of a ladder with n rungs. You can climb the ladder by taking 1 step, 2 steps or 3 steps at a time. Count the number of distinct ways you can reach the top of the ladder (i.e., the nth rung).

Simplified Version Approach

So, being on the last step (the nth) we could only have come from rungs n-1, n-2 or n-3

So, the number of ways to reach the nth rung is the sum of:

• number of ways to reach rung n-1 (if n>=1) - then take 1 step

• number of ways to reach rung n-2 (if n>=2) - then take 2 steps

• number of ways to reach rung n-3 (if n>=3) - then take 3 steps

Example: a 5-rung ladder

The number of ways to reach rung 1 is 1

• take 1 step

The number of ways to reach rung 2 is 2

• take 1 step → number of ways to reach rung 1 (1)

• take 2 steps

The number of ways to reach rung 3 is 4

• take 1 step → the number of ways to reach rung 2 (2)

• take 2 steps → the number of ways to reach rung 1 (1)

• take 3 steps

The number of ways to reach rung 4 is 7

• take 1 step → the number of ways to reach rung 3 (4)

• take 2 steps → the number of ways to reach rung 2 (2)

• take 3 steps → the number of ways to reach rung 1 (1)

The number of ways to reach rung 5 is 13

• take 1 step → the number of ways to reach rung 4 (7)

• take 2 steps → the number of ways to reach rung 3 (4)

• take 3 steps → the number of ways to reach rung 2 (2)

Code

First of all, we need to define the simplest case. That is the number of ways to reach rung 0 and it is equal to 1 as there is a single way to climb 0 rungs. Then, we just write the above.

In python that could be written like:

def count_ways(n):
    if n == 0:
        return 1
    ways_cnt = 0
    if n >= 1:
        ways_cnt += count_ways(n-1)
    if n >= 2:
        ways_cnt += count_ways(n-2)
    if n >= 3:
        ways_cnt += count_ways(n-3)
    return ways_cnt

As you can notice in the code and the example above, recursive calls result in some values being calculated multiple times which is undesirable especially when we seek performance. One way to cope with that is by calculating sequantially values for rungs 1, 2, 3, …, n. This works since for any particular rung i we need the values for rungs i-1, i-2, i-3 which have already been calculated.

def count_ways(n):
    dp = [0] * (n + 1)
    dp[0] = 1

    for i in range(1, n + 1):
        if i >= 1:
            dp[i] += dp[i-1]
        if i >= 2:
            dp[i] += dp[i-2]
        if i >= 3:
            dp[i] += dp[i-3]

    return dp[n]

To avoid code duplication this could be rewritten as:

def count_ways(n):
    dp = [0] * (n + 1)
    dp[0] = 1

    for i in range(1, n + 1):
        for j in range(1, 4):
            if i >= j:
                dp[i] += dp[i-j]

    return dp[n]

Solving the Original Problem

Now, to solve the original problem (possible climbing of 1, 2, …, k steps at a time instead of just 1, 2 or 3), we need to just change the range of j to be from 1 to k:

def count_ways(n, k):
    dp = [0] * (n + 1)
    dp[0] = 1

    for i in range(1, n + 1):
        for j in range(1, k + 1):
            if i >= j:
                dp[i] += dp[i-j]

    return dp[n]