DP solves a problem from smaller overlapping subproblems and stores the answers. Coin change: best[a] is fewest coins for amount a.

Goal

Compute fewest coins for 30 KES, and count paths in a tiny grid.

Coin change

def coins(amount, denoms):
    inf = amount + 1
    best = [0] + [inf] * amount
    for a in range(1, amount + 1):
        for d in denoms:
            if d <= a and best[a - d] + 1 < best[a]:
                best[a] = best[a - d] + 1
    return best[amount] if best[amount] < inf else -1

print(coins(30, [1, 5, 10, 20]))
print(coins(30, [1, 10, 25]))
print(coins(3, [5]))

Time Θ(amount × |denoms|). Space Θ(amount).

Grid paths

def paths(rows, cols):
    g = [[0] * cols for _ in range(rows)]
    for r in range(rows):
        g[r][0] = 1
    for c in range(cols):
        g[0][c] = 1
    for r in range(1, rows):
        for c in range(1, cols):
            g[r][c] = g[r - 1][c] + g[r][c - 1]
    return g[-1][-1]

print(paths(2, 3))
print(paths(3, 3))

Only right and down. Each cell sums the two ways in. Recursion without a table would recompute the same cell many times.

Tip

Ask: “does the best answer for n use a best answer for something smaller?” If yes, try DP. If choices do not overlap, maybe divide and conquer.