Project: Overview
- Algorithms course
- Advanced
- Lesson 17/56
- 4 min
Plan a mini route planner using DP.
Project: Route planner
In this project you will build a route planner application. You will find the lowest-cost path among four cities using dynamic programming.
Each lesson builds on the previous one: your code grows each step and you end up with a working route planner.
Cost table
We will store the costs between cities in a table. cost[i][j] is the cost of going from i to j. The diagonal is zero because there is no cost to stay in the same city.
This table is the basis of the dynamic programming solution. By returning the table from a function, we make it accessible everywhere.
Practice init_cities function
Write init_cities(). Return the list ['A', 'B', 'C', 'D']. Print it with print(init_cities()).
Starter code
def init_cities():
# Return city listSample solution
def init_cities():
# Return city list
return ['A', 'B', 'C', 'D']
print(init_cities())Expected output
['A', 'B', 'C', 'D']
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 What is the goal of the project?
- Find the lowest-cost path Correct answer
- Draw a tree
- Sort cities
- Generate random numbers
Explanation: The goal is to find the lowest-cost path.
2 City list function
init_____() returns the city listinit_cities() returns the city listExplanation: cities is right.
3 Project: Overview: match the terms
| Term | Meaning |
|---|---|
init_cities |
City list |
init_cost |
Cost table |
dp_min_cost |
Lowest cost |
print_route |
Print result |