DP solution

Compute the cheapest route with DP.

DP definition

dp[i] is the lowest cost to reach city i from the start. Initially dp[0] = 0 because we are at the start city.

For each i, we pick the lowest among all paths coming from smaller j. This is the optimal substructure property.

Recurrence relation

The DP recurrence is: dp[i] = min(dp[j] + cost[j][i]) for all j < i. For each i, we try every earlier city and pick the best.

This formula uses the overlapping subproblems property. Each subproblem is computed only once.

Exercise dp_min_cost function

Write dp_min_cost(cost). Build dp array using dp[i] = min(dp[j] + cost[j][i]). Print 55 with print(dp_min_cost(init_cost())).

Show example solution

def init_cities():
    # Return city list
    return ['A', 'B', 'C', 'D']
def init_cost():
    # Return cost matrix
    return [[0, 10, 25, 60], [0, 0, 20, 50], [0, 0, 0, 30], [0, 0, 0, 0]]
def dp_min_cost(cost):
    # Find the lowest cost
    n = len(cost)
    dp = [0] * n
    for i in range(1, n):
        best = float('inf')
        for j in range(i):
            cand = dp[j] + cost[j][i]
            if cand < best:
                best = cand
        dp[i] = best
    return dp[n - 1]
print(dp_min_cost(init_cost()))

Test yourself

DP solution: match the terms

dp[0]

0
dp[1]

10
dp[2]

25
dp[3]

55
What is the lowest cost from A to D?
- 60
- 50
- 55
- 30
Show answer

55 — Path A→C→D gives 25+30=55.
Inner loop variable
```
for j in ____(i):
```
Show answer
```
for j in range(i):
```

Next lesson: Print the result

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies