Traveling Salesman Problem
Learn Traveling Salesman Problem (Dynamic Programming, Advanced DSA) with worked examples, diagrams and interview questions. Free on JavaSchoolLab.
Visit Every City Exactly Once, Minimize Total Distance Brute force tries all n! orderings. Bitmask DP reduces this to O(2ⁿ × n²): the STATE is (mask, current city) , where mask is a BITMASK recording which cities have been visited. Since only "which cities visited so far" and "where I am now" matter (not the exact visiting ORDER), this compresses the state space enormously.
More lessons in Dynamic Programming
- Fibonacci (DP)
- Climbing Stairs
- House Robber
- Kadane (DP)
- Grid Paths
- Unique Paths
- Minimum Path Sum
- 0/1 Knapsack
- Unbounded Knapsack
- Bounded Knapsack
- Subset Sum
- Equal Partition
- Target Sum
- Longest Common Subsequence - LCS
- Longest Common Substring
- Edit Distance
- Longest Palindromic Subsequence
- Palindrome Partitioning
- Longest Increasing Subsequence - LIS
- Number of LIS
- Maximum Sum Increasing Subsequence
- Matrix Chain Multiplication
- Burst Balloons
- Optimal BST
- Diameter (Tree DP)
- Maximum Path Sum (Tree DP)
- Tree Independent Set
- Assignment Problems
- Counting Numbers (Digit DP)
- Digit Constraints