Day 61 of 100 days dsa coding challenge

Taking on a new challenge: solving GeeksforGeeks POTD daily and sharing my solutions! 💻🔥
The goal: sharpen problem-solving skills, level up coding, and learn something new every day. Follow my journey! 🚀

100DaysOfCode #CodingChallenge #ProblemSolving #GeeksforGeeks #DeveloperJourney

*Problem: *
https://www.geeksforgeeks.org/problems/travelling-salesman-problem2732/1

Travelling Salesman Problem

Difficulty: Hard Accuracy: 46.35%

Given a 2d matrix cost[][] of size n where cost[i][j] denotes the cost of moving from city i to city j. Your task is to complete a tour from city 0 (0-based index) to all other cities such that you visit each city exactly once and then at the end come back to city 0 at minimum cost.
Examples:
Input: cost[][] = [[0, 111],
[112, 0]]
Output: 223
Explanation: We can visit 0->1->0 and cost = 111 + 112.
Input: cost[][] = [[0, 1000, 5000],
[5000, 0, 1000],
[1000, 5000, 0]]
Output: 3000
Explanation: We can visit 0->1->2->0 and cost = 1000 + 1000 + 1000 = 3000
Constraints:
1 ≤ cost.size() ≤ 15
0 ≤ cost[i][j] ≤ 104

Solution:
class Solution:
def tsp(self, cost):
n = len(cost)
m = 1 << n
dp = [[10**15] * n for _ in range(m)]
dp[1][0] = 0
for mask in range(m):
for u in range(n):
if mask & (1 << u):
for v in range(n):
if not (mask & (1 << v)):
nxt = mask | (1 << v)
dp[nxt][v] = min(dp[nxt][v], dp[mask][u] + cost[u][v])
ans = min(dp[m-1][i] + cost[i][0] for i in range(n))
return ans