DP solution
- Algorithms course
- Advanced
- Lesson 19/56
- 4 min
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.
Practice 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())).
Starter code
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 costSample 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()))Expected output
55
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 DP solution: match the terms
| Term | Meaning |
|---|---|
dp[0] |
0 |
dp[1] |
10 |
dp[2] |
25 |
dp[3] |
55 |
2 What is the lowest cost from A to D?
- 60
- 50
- 55 Correct answer
- 30
Explanation: Path A→C→D gives 25+30=55.
3 Inner loop variable
for j in ____(i):for j in range(i):Explanation: range is right.