Dynamic programming (DP) is an algorithmic technique for solving problems that exhibit overlapping subproblems and optimal substructure. Overlapping subproblems mean the same smaller instances are solved repeatedly, while optimal substructure implies that an optimal solution to the larger problem can be constructed from optimal solutions of its subproblems.

Consider a staircase with n steps where you can climb either 1 or 2 steps at a time. The total number of distinct ways to reach the top follows the recurrence:

f(n) = f(n-1) + f(n-2)

This is because the last move must come from either step n-1 (with a 1-step jump) or step n-2 (with a 2-step jump). The base cases are f(0) = 1 (one way to stay at ground level) and f(1) = 1.

The approach generalizes easily:

• If allowed steps are {1, 2, 4}, then f(n) = f(n-1) + f(n-2) + f(n-4).
• If allowed steps are {1, k}, then f(n) = f(n-1) + f(n-k) (when n ≥ k).
• If allowed steps are {1, 2, ..., k}, then f(n) = sum(f(n-i)) for i in 1..k (when n ≥ i).

Core DP Steps

1. Decompose the problem into smaller subproblems.
2. Define state: e.g., dp[i] = number of ways to reach step i.
3. Formulate recurrence: how dp[i] depends on previous states.
4. Implement iteratively or via memoization.

Broken Staircase Problem

Some steps are broken and cannot be stepped on. Let blocked[i] = True if step i is unusable.

MOD = 10**9 + 7
n, m = map(int, input().split())
blocked = [False] * (n + 1)
for x in map(int, input().split()):
    if x <= n:
        blocked[x] = True

dp = [0] * (n + 1)
dp[0] = 1
if n >= 1:
    dp[1] = 0 if blocked[1] else 1

for i in range(2, n + 1):
    if blocked[i]:
        continue
    dp[i] = (dp[i - 1] + dp[i - 2]) % MOD

print(dp[n])

For input:

6 1
3

The output is 4, as step 3 is blocked, eliminating paths that land on it.

Safe Sequence Problem

You're placing markers on positions 1 to n. After placing a marker, the next one must be at least k+1 postiions ahead. Count valid sequences.

Here, dp[i] = number of valid sequences ending at or before position i.

MOD = 10**9 + 7
n, k = map(int, input().split())
dp = [0] * (n + 1)
dp[0] = 1

for i in range(1, n + 1):
    # Option 1: don't place at i → carry over dp[i-1]
    # Option 2: place at i → last placement must be ≤ i - (k+1)
    prev = dp[i - k - 1] if i - k - 1 >= 0 else 1
    dp[i] = (dp[i - 1] + prev) % MOD

print(dp[n])

For input:

4 2

Output is 6, representing all valid placement patterns under the spacing constraint.